Em 1936, o cientista Alan Turing, em sua publicação “On Computable Numbers, With An Application to Entscheidungsproblem”, descreve o uso de uma máquina de computação universal que poderia pôr fim ao problema de solubilidade em matemática. Como resultado, ele chega à conclusão de que tal máquina não seria capaz de resolver nada corretamente se o resultado de seu trabalho fosse invertido e girado sobre si mesmo. Acontece que é impossível criar um antivírus *ideal*, um configurador de blocos *ideal*, um programa que sugira frases ideais para o seu travamento, etc. Paradoxo!
No entanto, esta máquina de computação universal pode ser usada para implementar qualquer algoritmo, do qual a inteligência britânica se aproveitou, contratando Turing e permitindo a criação de uma máquina “Bombe” para decifrar mensagens alemãs durante a Segunda Guerra Mundial.
A seguir está a modelagem OOP de um computador de fita única na linguagem Dart, com base no documento original.
Uma máquina de Turing consiste em um filme dividido em seções, cada seção contém um símbolo, os símbolos podem ser lidos ou escritos. Exemplo de aula de cinema:
final _map = Map<int, String>();
String read({required int at}) {
return _map[at] ?? "";
}
void write({required String symbol, required int at}) {
_map[at] = symbol;
}
}
Existe também um “quadrado de digitalização”, que pode mover-se pelo filme, ler ou escrever informações, em linguagem moderna – cabeça magnética. Exemplo de classe de cabeça magnética:
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;
}
}
A máquina contém “m-configurações” pelas quais ela pode decidir o que fazer em seguida. Na linguagem moderna – estados e manipuladores de estado. Exemplo de manipulador de estado:
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();
и т.д.
Depois disso, você precisa criar “configurações”, em linguagem moderna são códigos de operação (opcodes) e seus manipuladores. Códigos de operação de exemplo:
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";
Não se esqueça de criar um opcode e um manipulador de parada, caso contrário você não será capaz de provar ou deixará de provar (sic!) a resolução do problema.
Agora, usando o padrão “mediador”, conectamos todas as classes da classe Turing Machine, criamos uma instância da classe, gravamos o programa através de um gravador, carregamos a fita e você pode usá-la!
Para mim, pessoalmente, a questão do que era primário permaneceu interessante – criação de uma calculadora universal ou prova do “Entscheidungsproblem” como resultado do qual, como subproduto, apareceu uma calculadora.
Cassetes
Para me divertir, gravei vários programas em fita cassete para minha versão da máquina.
Olá, mundo
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
Escrevendo em Assembly para Sega Genesis #5
Nesta nota descreverei o processo de leitura do joystick, mudança de posição do sprite, giro horizontal, emulador Sega Genesis e potencialmente o próprio console.
A leitura de cliques e o processamento de “eventos” de um joystick shogi ocorre de acordo com o seguinte esquema:
- Solicitação de uma combinação de bits de botões pressionados
- Lendo pedaços de botões pressionados
- Processamento no nível lógico do jogo
Para mover o sprite do esqueleto, precisamos armazenar variáveis da posição atual.
RAM
As variáveis lógicas do jogo são armazenadas na RAM; até agora as pessoas não encontraram nada melhor. Vamos declarar endereços de variáveis e alterar o código de renderização:
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
Como você pode ver, o endereço disponível para trabalho começa em 0xFF0000 e termina em 0xFFFFFF, no total temos 64 KB de memória disponíveis. As posições do esqueleto são declaradas em esqueletoXpos, esqueletoYpos, rotação horizontal em esqueletoHorizontalFlip.
Joypad
Por analogia com o VDP, o trabalho com joypads ocorre através de duas portas separadamente – porta de controle e porta de dados, para a primeira 0xA10009 e 0xA10003 co-no. Há um recurso interessante ao trabalhar com um joypad: Primeiro você precisa solicitar uma combinação de botões para polling e, em seguida, após aguardar uma atualização no barramento, ler os pressionamentos necessários. Para os botões C/B e D-pad é 0x40, exemplo abaixo:
move.b #$40,joypad_one_control_port; C/B/Dpad
nop ; bus sync
nop ; bus sync
move.b joypad_one_data_port,d2
rts
No registro d2 permanecerá o estado dos botões pressionados ou não pressionados, em geral permanecerá o que foi solicitado através da porta data. Depois disso, vá até o visualizador de registros Motorola 68000 do seu emulador favorito, veja a que é igual o registro d2, dependendo das teclas digitadas. De forma inteligente, você pode descobrir no manual, mas não acreditamos apenas na palavra deles. Processamento adicional de botões pressionados no registro d2
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
Depois disso, o esqueleto fica mais lento, o que era necessário. Como eu sei, a opção mais comum para “desacelerar” é contar o sinalizador de sincronização vertical, você pode contar quantas vezes a tela foi desenhada, ficando assim vinculada a um fps específico.
Links
https://gitlab .com/demensdeum/segagenesisamples/-/blob/main/8Joypad/vasm/main.asm
Fontes
https://www.chibiakumas.com/68000/platform2.php
https://huguesjohnson.com/programming/genesis/tiles-sprites/
Escrevendo em Assembly para Sega Genesis #4
Neste post irei descrever como desenhar sprites usando o emulador VDP do console Sega Genesis.
O processo de renderização de sprites é muito semelhante ao de renderização de blocos:
- Carregando cores no CRAM
- Enviando partes dos sprites 8×8 para VRAM
- Preenchendo Tabela Sprite na VRAM
Por exemplo, vamos pegar um sprite de um esqueleto com uma espada de 32×32 pixels
Skeleton Guy [Animated] by Disthorn
CRAM
Usando ImaGenesis, vamos convertê-lo em cores CRAM e padrões VRAM para assembler. Depois disso, obteremos dois arquivos no formato asm, depois reescreveremos as cores no tamanho da palavra, e os ladrilhos deverão ser colocados na ordem correta para o desenho.
Informação interessante: você pode mudar o incremento automático de VDP através do registro 0xF para o tamanho da palavra, isso removerá o incremento de endereço do código de preenchimento de cores CRAM.
VRAM
O manual do Shogi tem a ordem correta dos blocos para sprites grandes, mas somos mais espertos, então pegaremos os índices do blog ChibiAkumas, vamos começar a contar a partir do índice 0:
0 4 8 12
1 5 9 13
2 6 10 14
3 7 11 15
Por que está tudo de cabeça para baixo? O que você quer, o console é japonês! Pode até ser da direita para a esquerda!
Vamos alterar manualmente a ordem no arquivo sprite asm:
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
и т.д.
Carregue o sprite como blocos/padrões normais:
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
Para desenhar um sprite, basta preencher a Tabela de Sprites
Tabela Sprite
A tabela de sprites é preenchida em VRAM, o endereço de sua localização é inserido no registrador VDP 0x05, o endereço é novamente complicado, você pode ver no manual, um exemplo para o endereço F000:
Ок, теперь запишем наш спрайт в таблицу. Для этого нужно заполнить “структуру” данных состоящую из четырех word. Бинарное описание структуры вы можете найти в мануале. Лично я сделал проще, таблицу спрайтов можно редактировать вручную в эмуляторе Exodus.
Os parâmetros da estrutura são óbvios pelo nome, por exemplo XPos, YPos – coordenadas, blocos – número do bloco inicial para desenho, HSize, VSize – tamanhos de sprite adicionando partes 8×8, HFlip, VFlip – rotação de hardware do sprite horizontal e verticalmente.
É muito importante lembrar que os sprites podem ficar fora da tela, esse é um comportamento correto, pois… descarrega sprites fora da tela da memória – uma atividade que consome muitos recursos.
Após preencher os dados no emulador, eles precisam ser copiados da VRAM para o endereço 0xF000, o Exodus também suporta esse recurso.
Por analogia com o desenho de blocos, primeiro acessamos a porta de controle VDP para começar a escrever no endereço 0xF000, depois escrevemos a estrutura na porta de dados.
Deixe-me lembrar que a descrição do endereçamento VRAM pode ser lida no manual ou no blog Algoritmo Sem Nome .
Resumindo, o endereçamento VDP funciona assim:
[..DC BA98 7654 3210 …. …. …. ..FE]
Onde hex é a posição do bit no endereço desejado. Os dois primeiros bits são o tipo de comando solicitado, por exemplo 01 – escreva para VRAM. Então para o endereço 0XF000 acontece:
0111 0000 0000 0000 0000 0000 0000 0011 (70000003)
Como resultado, obtemos o código:
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
Depois disso, o sprite do esqueleto será exibido nas coordenadas 256, 256. Legal, certo?
Links
https://gitlab.com/demensdeum /segagenesissamples/-/tree/main/7Sprite/vasm
https://opengameart.org/content/skeleton-guy-animated
Fontes
https://namelessalgorithm.com/genesis/blog/vdp/https://www.chibiakumas.com/68000/platform3.php#LessonP27
https://plutiedev.com/sprites
Escrevendo em Assembly para Sega Genesis #3
Neste post irei descrever como exibir uma imagem de blocos no emulador Sega Genesis usando assembler.
A imagem inicial do Demens Deum no emulador Exodus terá esta aparência:
O processo de saída de uma imagem PNG usando blocos é feito passo a passo:
- Reduzindo a imagem para o tamanho da tela do Shogi
- Converta PNG em código de dados assembly, separado em cores e blocos
- Carregando uma paleta de cores no CRAM
- Carregando blocos/padrões na VRAM
- Carregando índices de blocos em endereços do plano A/B na VRAM
- Você pode reduzir a imagem para o tamanho da tela do Shogi usando seu editor gráfico favorito, como o Blender.
Conversão de PNG
Para converter imagens, você pode usar a ferramenta ImaGenesis; para trabalhar no wine, são necessárias bibliotecas Visual Basic 6, elas podem ser instaladas usando winetricks (winetricks vb6run), ou RICHTX32.OCX pode ser baixado da Internet e colocado em a pasta do aplicativo para operação correta.< /p>
No ImaGenesis você precisa selecionar cores de 4 bits, exportar cores e blocos para dois arquivos no formato assembler. A seguir, no arquivo com cores, você precisa colocar cada cor em uma palavra (2 bytes), para isso utiliza o opcode dc.w.
Por exemplo, tela inicial do CRAM:
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
Deixe o arquivo de blocos como está, ele já contém o formato correto para carregamento. Exemplo de parte de um arquivo de blocos:
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
Como você pode ver no exemplo acima, os blocos são uma grade 8×8 que consiste em índices da paleta de cores CRAM.
Cores no CRAM
O carregamento na CRAM é feito configurando um comando de carregamento de cores para um endereço CRAM específico na porta de controle (controle vdp). O formato do comando está descrito no Sega Genesis Software Manual (1989), apenas acrescentarei que você só precisa adicionar 0x20000 ao endereço para passar para a próxima cor.
Em seguida você precisa carregar a cor na porta de dados (dados vdp); A maneira mais fácil de entender o carregamento é com o exemplo abaixo:
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
Telhas em VRAM
A seguir, carregamos blocos/padrões na memória de vídeo VRAM. Para fazer isso, selecione um endereço na VRAM, por exemplo 0x00000000. Por analogia com a CRAM, entramos em contato com a porta de controle VDP com um comando para escrever na VRAM e no endereço inicial.
Depois disso, você pode fazer upload de palavras longas para VRAM; em comparação com CRAM, não é necessário especificar o endereço de cada palavra longa, pois existe um modo de incremento automático de VRAM. Você pode habilitá-lo usando o sinalizador de registro VDP 0x0F (dc.b $02)
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
Índices de blocos no plano A/B
Agora temos que preencher a tela com blocos de acordo com seu índice. Para isso, a VRAM é preenchida no endereço do Plano A/B, que é inserido nos registradores VDP (0x02, 0x04). Mais informações sobre endereçamento complicado estão no manual da Sega; no meu exemplo, o endereço VRAM é 0xC000, vamos fazer upload dos índices lá.
Sua imagem preencherá o espaço VRAM fora da tela de qualquer maneira, então depois de desenhar o espaço da tela, seu renderizador deverá parar de desenhar e continuar novamente quando o cursor se mover para uma nova linha. Existem muitas opções de como implementar isso; usei a versão mais simples de contagem em dois registros do contador de largura da imagem e do contador de posição do cursor.
Exemplo de código:
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
Depois disso, só falta montar a rom usando o vasm, iniciar o simulador e ver a foto.
Depuração
Nem tudo vai dar certo imediatamente, então eu gostaria de recomendar as seguintes ferramentas do emulador Exodus:
- Depurador de processador M68k
- Alterando o número de ciclos do processador m68k (para modo câmera lenta no depurador)
- Visualizadores CRAM, VRAM, Plano A/B
- Leia atentamente a documentação do m68k, os opcodes usados (nem tudo é tão óbvio quanto parece à primeira vista)
- Veja exemplos de código/desmontagem do jogo no github
- Implementar sub-rotinas de exceções do processador e processá-las
Ponteiros para sub-rotinas de exceção do processador são colocados no cabeçalho da rom. Há também um projeto no GitHub com um depurador de tempo de execução interativo para Sega, chamado genesis-debugger.
Use todas as ferramentas disponíveis, tenha uma boa codificação à moda antiga e que o Blast Processing esteja com você!
Links
https://gitlab.com/demensdeum /segagenesisamples/-/tree/main/6Image/vasm
http://devster.monkeeh.com/sega/imagenesis/
https://github.com/flamewing/genesis-debugger
Fontes
https://www.chibiakumas.com/68000/helloworld .php#LessonH5
https://huguesjohnson.com/programming/genesis/tiles-sprites/
Escrevendo em Assembly para Sega Genesis #2
Neste post irei descrever como carregar cores na paleta Shogi em linguagem assembly.
O resultado final no emulador Exodus ficará assim:
Para facilitar o processo, encontre um pdf na Internet chamado Genesis Software Manual (1989), ele descreve todo o processo detalhadamente, na verdade, esta nota é um comentário ao manual original.< /p>
Para gravar cores no chip VDP do emulador Sega, você precisa fazer o seguinte:
- Desativar proteção TMSS
- Escrever parâmetros corretos nos registros VDP
- Escreva as cores desejadas no CRAM
Para montagem usaremos vasmm68k_mot e um editor de texto favorito, por exemplo echo. A montagem é realizada com o comando:
Порты VDP
VDP чип общается с M68K через два порта в оперативной памяти – порт контроля и порт данных.
По сути:
- Через порт контроля можно выставлять значения регистрам VDP.
- Также порт контроля является указателем на ту часть VDP (VRAM, CRAM, VSRAM etc.) через которую передаются данные через порт данных
Интересная информация: Сега сохранила совместимость с играми 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
Escrever parâmetros corretos nos registros VDP
Por que definir os parâmetros corretos nos registros VDP? A ideia é que o VDP pode fazer muita coisa, então antes de renderizar você precisa inicializá-lo com os recursos necessários, caso contrário ele simplesmente não entenderá o que querem dele.
Cada registro é responsável por um modo de configuração/operação específico. O manual do Segov indica todos os bits/sinalizadores para cada um dos 24 registros, uma descrição dos próprios registros.
Vamos usar parâmetros prontos com comentários do blog bigevilcorporation:
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, agora vamos para a porta de controle e escrever todas as flags nos registradores VDP:
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; Отправляем цвет в порт данных
Depois de construir e executar o emulador no Exodus, sua tela deverá ser preenchida com a cor 228.
Vamos preenchê-lo com uma segunda cor, com base no último 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
Fontes
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/
Escrevendo em Assembly para Sega Genesis #1
O primeiro artigo dedicado a escrever jogos para o clássico console Sega Genesis em Motorola 68000 Assembly.
Vamos escrever o loop infinito mais simples para a Sega. Para isso precisaremos de: um montador, um emulador com desmontador, um editor de texto favorito, um conhecimento básico da estrutura do Sega rum.
Para desenvolvimento eu uso meu próprio montador/desmontador Gen68KryBaby:
https://gitlab.com/demensdeum/gen68krybaby/
A ferramenta é desenvolvida em Python 3, para montagem é fornecido como entrada um arquivo com extensão .asm ou .gen68KryBabyDisasm, a saída é um arquivo com extensão .gen68KryBabyAsm.bin, que pode ser executado no emulador ou em um console real (tenha cuidado, afaste-se, o console pode explodir!)
A desmontagem de roms também é suportada, para isso você precisa enviar um arquivo rom como entrada, sem as extensões .asm ou .gen68KryBabyDisasm. O suporte ao Opcode aumentará ou diminuirá dependendo do meu interesse no tópico e da participação dos colaboradores.
Estrutura
O cabeçalho rom da Sega ocupa os primeiros 512 bytes. Ele contém informações sobre o jogo, nome, periféricos suportados, soma de verificação e outros sinalizadores do sistema. Presumo que sem título o console nem vai olhar para o rum, pensando que está incorreto, dizendo “o que você está me dando aqui?”
Depois do cabeçalho vem a sub-rotina/Reset sub-rotina, que é onde o processador m68K inicia seu trabalho. Ok, é uma questão pequena – encontrar opcodes (códigos de operação), ou seja, não fazer nada (!) e mudar para a sub-rotina no endereço da memória. Pesquisando no Google, você encontra o opcode NOP, que não faz nada, e o opcode JSR, que realiza um salto incondicional para o endereço do argumento, ou seja, simplesmente move o carro para onde solicitamos, sem nenhum capricho.
Juntando tudo
O doador de cabeçalho da rom foi um dos jogos da versão Beta, atualmente registrado como dados hexadecimais.
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
Exemplo completo junto com o cabeçalho da rom:
https://gitlab.com /demensdeum/segagenesisamples/-/blob/main/1InfiniteLoop/1infiniteloop.asm
Coletamos a seguir:
Запускаем ром 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
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
Como senti falta do cara no poste ou de uma história sobre uma engenhosidade incrível
Nesta nota escreverei sobre a importância das decisões arquitetônicas ao desenvolver, dar suporte a um aplicativo e em um ambiente de desenvolvimento de equipe.
Auto- guardanapo operacional Professor Lucifer Gorgonzola. Rube Goldberg
Durante minha juventude, trabalhei em um aplicativo de pedido de táxi. No programa você pode selecionar um ponto de coleta, um ponto de entrega, calcular o custo da viagem, o tipo de tarifa e, de fato, pedir um táxi. Recebi o aplicativo na última etapa de pré-lançamento, após adicionar diversas correções, o aplicativo foi lançado na AppStore; Já nessa fase, toda a equipe entendeu que estava muito mal implementado, não eram utilizados padrões de projeto, todos os componentes do sistema estavam intimamente conectados, em geral era possível escrevê-lo em uma grande classe contínua (objeto Deus), nada teria mudado, portanto, a forma como as classes misturavam os seus limites de responsabilidade e, na sua massa total, sobrepunham-se umas às outras num acoplamento morto. Posteriormente, a administração decidiu escrever a aplicação do zero, utilizando a arquitetura correta, o que foi feito e o produto final foi implementado para várias dezenas de clientes B2B.
No entanto, descreverei um incidente curioso da arquitetura do passado, do qual às vezes acordo suando frio no meio da noite, ou de repente me lembro no meio do dia e começo a rir histericamente. O problema é que não consegui acertar o cara no poste da primeira vez, e isso derrubou a maior parte do aplicativo, mas o mais importante primeiro.
Era um dia normal de trabalho, um dos clientes recebeu a tarefa de refinar um pouco o design do aplicativo. É trivial mover o ícone no centro da tela de seleção do endereço de coleta alguns pixels para cima. Bem, tendo estimado profissionalmente a tarefa em 10 minutos, levantei o ícone 20 pixels para cima, sem suspeitar de nada, resolvi verificar a ordem do táxi.
O quê? O aplicativo não mostra mais o botão de pedido? Como isso aconteceu?
Eu não conseguia acreditar no que via; depois de aumentar o ícone em 20 pixels, o aplicativo parou de mostrar o botão continuar pedido. Depois de reverter a alteração, vi o botão novamente. Algo estava errado aqui. Depois de passar 20 minutos no depurador, fiquei um pouco cansado de desenrolar o espaguete de chamadas para classes sobrepostas, mas descobri que *mover a imagem realmente muda a lógica da aplicação*
Tudo girava em torno do ícone no centro – um homem em um poste, ao movimentar a carta ele pulou para animar o movimento da câmera, essa animação foi seguida pelo desaparecimento do botão na parte inferior. Aparentemente o programa pensou que o homem deslocado em 20 pixels estava pulando, então de acordo com sua lógica interna ele escondeu o botão de confirmação.
Como isso pode acontecer? Será que o *estado* da tela realmente não depende do padrão da máquina de estado, mas da *representação* da posição do homem no mastro?
Acontece que assim, toda vez que o mapa é desenhado, o aplicativo *cutucou visualmente* no meio da tela e verificou o que estava lá, se houver um homem em um poste, significa que a animação de mudança do mapa terminou e precisa ser mostrada botão. Se o homem não estiver lá, o mapa será deslocado e o botão deverá ser ocultado.
No exemplo acima, está tudo bem, em primeiro lugar, é um exemplo de Máquinas Goldberg (máquinas obscuras), em segundo lugar, um exemplo da relutância do desenvolvedor em interagir de alguma forma com outros desenvolvedores da equipe (tente descobrir sem eu), em terceiro lugar, você pode listar todos os problemas de acordo com o SOLID, padrões (cheiros de código), violações de MVC e muito mais.
Tente não fazer isso, desenvolva-se em todas as direções possíveis, ajude seus colegas no trabalho. Feliz Ano Novo a todos)
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
Adivinhe o grupo
Nesta postagem descreverei como trabalhar com o classificador de texto fasttext.
Texto rápido – biblioteca de aprendizado de máquina para classificação de texto. Vamos tentar ensiná-la a identificar uma banda de metal pelo título da música. Para fazer isso, usamos aprendizagem supervisionada usando um conjunto de dados.
Vamos criar um conjunto de dados de músicas com nomes de grupos:
__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")
Carregue o modelo treinado e peça para identificar o grupo pelo nome da música:
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 Montador + C = Um Amor
Nesta nota descreverei o processo de chamada de funções C a partir do assembler.
Vamos tentar chamar printf(“Hello World!\n”); e sair(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
Tudo é muito mais simples do que parece, na seção .rodata iremos descrever dados estáticos, neste caso a linha “Hello, world!”, 10 é um caractere de nova linha, e também não esquecemos de anulá-lo.
Na seção de código declararemos as funções externas printf, exit das bibliotecas stdio, stdlib e também declararemos a função de entrada main:
extern printf
extern exit
global main
Passamos 0 para o registrador de retorno da função rax, você pode usar mov rax, 0; mas para acelerar eles usam xor rax, rax; A seguir, passamos um ponteiro para a string do primeiro argumento:
Далее вызываем внешнюю функцию Си printf:
xor rax, rax
mov rdi, message
call printf
xor rdi, rdi
call exit
Por analogia, passamos 0 para o primeiro argumento e chamamos exit:
call exit
Como dizem os americanos:
Quem não escuta ninguém
Esse pilaf está comendo @ Alexander Pelevin
Fontes
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
Código fonte
https://gitlab.com/demensdeum/assembly-playground
Olá mundo montador x86_64
Neste post irei descrever o processo de configuração do IDE, escrevendo o primeiro Hello World em assembler x86_64 para o sistema operacional Ubuntu Linux.
Vamos começar instalando o IDE SASM, montador nasm:
Далее запустим 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
Código Hello World retirado do blog James Fisher, adaptado para montagem e depuração em SASM. A documentação do SASM afirma que o ponto de entrada deve ser uma função chamada main, caso contrário a depuração e compilação do código serão incorretas.
O que fizemos neste código? Fez uma chamada syscall – acesso ao kernel do sistema operacional Linux com argumentos corretos nos registros, um ponteiro para uma string na seção de dados.
Sob uma lupa
Vejamos o código com mais detalhes:
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
Tabela hash
A tabela hash permite implementar uma estrutura de dados de array associativo (dicionário) com desempenho médio O(1) para operações de inserção, exclusão e pesquisa.
Abaixo está um exemplo da implementação mais simples de um mapa hash em nodeJS:
Como funciona? Cuidado com as mãos:
- Dentro do mapa hash há um array
- Dentro do elemento array há um ponteiro para o primeiro nó da lista vinculada
- A memória é alocada para uma matriz de ponteiros (por exemplo, 65.535 elementos)
- Eles implementam uma função hash, a chave do dicionário é a entrada e na saída pode fazer qualquer coisa, mas no final retorna o índice do elemento do array
Como funciona a gravação:
- Na entrada há um par de chaves – valor
- A função hash retorna índice por chave
- Obter um nó de lista vinculada de um array por índice
- Verifique se corresponde à chave
- Se corresponder, substitua o valor
- Se não corresponder, passe para o próximo nó até encontrarmos ou encontrarmos um nó com a chave necessária.
- Se o nó ainda não for encontrado, crie-o no final da lista vinculada
Como funciona a pesquisa por chave:
- Na entrada há um par de chaves – valor
- A função hash retorna índice por chave
- Obter um nó de lista vinculada de um array por índice
- Verifique se corresponde à chave
- Se corresponder, retorne o valor
- Se não corresponder, passe para o próximo nó até encontrarmos ou encontrarmos um nó com a chave necessária.
Por que precisamos de uma lista vinculada dentro de um array? Devido a possíveis colisões ao calcular a função hash. Nesse caso, vários pares de valores-chave diferentes estarão localizados no mesmo índice da matriz, caso em que a lista vinculada é percorrida para encontrar a chave necessária.
Fontes
https://ru.wikipedia.org/wiki/Tabela hash
https://www.youtube.com/watch?v=wg8hZxMRwcw
Código fonte
https://gitlab.com/demensdeum/datastructures
Trabalhando com recursos em Android C++
Para trabalhar com recursos no Android via ndk – C++ existem várias opções:
- Use o acesso aos recursos de um arquivo apk usando o AssetManager
- Baixe recursos da Internet e descompacte-os no diretório do aplicativo, use-os usando métodos C++ padrão
- Método combinado – acesse o arquivo com recursos no apk via AssetManager, descompacte-os no diretório do aplicativo e use-os usando métodos C++ padrão
A seguir descreverei o método de acesso combinado usado no motor de jogo Flame Steel Engine.
Ao usar SDL, você pode simplificar o acesso aos recursos de um apk; a biblioteca agrupa chamadas para o AssetManager, oferecendo interfaces semelhantes ao stdio (fopen, fread, fclose, etc.)
SDL_RWops *io = SDL_RWFromFile("files.fschest", "r");
Depois de baixar o arquivo do apk para o buffer, você precisa alterar o diretório de trabalho atual para o diretório do aplicativo, ele fica disponível para o aplicativo sem obter permissões adicionais. Para fazer isso, usaremos um wrapper SDL:
chdir(SDL_AndroidGetInternalStoragePath());
Em seguida, grave o arquivo do buffer no diretório de trabalho atual usando fopen, fwrite, fclose. Assim que o arquivo estiver em um diretório acessível ao C++, descompacte-o. Os arquivos Zip podem ser descompactados usando uma combinação de duas bibliotecas – – minizip e zlib, o primeiro pode trabalhar com a estrutura de arquivos, enquanto o segundo descompacta dados.
Para obter mais controle e facilidade de portabilidade, implementei meu próprio formato de arquivo de compactação zero chamado FSChest (Flame Steel Chest). Este formato suporta arquivar um diretório com arquivos e descompactá-lo; Não há suporte para hierarquia de pastas; você só pode trabalhar com arquivos.
Conectamos o cabeçalho da biblioteca FSChest, descompacte o arquivo:
#include "fschest.h"
FSCHEST_extractChestToDirectory(archivePath, SDL_AndroidGetInternalStoragePath());
Após a descompactação, as interfaces C/C++ terão acesso aos arquivos do arquivo. Assim, não precisei reescrever todo o trabalho com arquivos no mecanismo, apenas adicionei a descompactação dos arquivos na fase de inicialização.
Fontes
https://developer.android.com/ndk/ referência/grupo/ativo
Código Fonte
https://gitlab.com/demensdeum/space- jaguar-action-rpg
https://gitlab.com/demensdeum/fschest
Máquina de empilhar e RPN
Suponha que precisemos implementar um interpretador de bytecode simples. Que abordagem devemos escolher para implementar essa tarefa?
Estrutura de dados A pilha fornece a capacidade de implementar uma máquina de bytecode simples. Os recursos e implementações de máquinas stack são descritos em muitos artigos na Internet ocidental e doméstica. Apenas mencionarei que a máquina virtual Java é um exemplo de máquina stack.
O princípio de funcionamento da máquina é simples, um programa contendo dados e códigos de operação (opcodes) é fornecido à entrada e as operações necessárias são implementadas por meio de manipulações com a pilha. Vejamos um exemplo de programa de bytecode da minha máquina de pilha:
пMVkcatS olleHП
Na saída receberemos a string “Hello StackVM”. A máquina de pilha lê o programa da esquerda para a direita, carregando dados caractere por caractere na pilha quando um opcode aparece no símbolo – implementa o comando usando a pilha.
Exemplo de implementação de uma máquina stack em nodejs:
Notação polonesa reversa (RPN)
As máquinas Stack também são fáceis de usar para implementar calculadoras, para isso utilizam a notação polonesa reversa (notação postfix).
Exemplo de notação infixa regular:
2*2+3*4
Converte para RPN:
22*34*+
Para contar o registro postfix usamos uma máquina de pilha:
2– para o topo da pilha (pilha: 2)
2– para o topo da pilha (pilha: 2,2)
*– pegue o topo da pilha duas vezes, multiplique o resultado, envie para o topo da pilha (pilha: 4)
3– para o topo da pilha (pilha: 4, 3)
4– para o topo da pilha (pilha: 4, 3, 4)
*– pegue o topo da pilha duas vezes, multiplique o resultado, envie-o para o topo da pilha (pilha: 4, 12)
+– pegue o topo da pilha duas vezes, some o resultado, envie-o para o topo da pilha (pilha: 16)
Como você pode ver – o resultado das operações 16 permanece na pilha, ele pode ser impresso implementando opcodes de impressão da pilha, por exemplo:
p22*34*+P
P – Código de operação de início de impressão da pilha, p – opcode para finalizar a impressão da pilha e enviar a linha final para renderização.
Para converter operações aritméticas de infixo para pós-fixo, é usado o algoritmo de Edsger Dijkstra chamado “Sorting Yard”. Um exemplo da implementação pode ser visto acima, ou no repositório do projeto de pilha de máquinas nodejs abaixo.
Fontes
https:/ /tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись
Código fonte
https://gitlab.com/demensdeum/stackvm/< /p>
Animação esquelética (Parte 2 – hierarquia de nós, interpolação)
Continuo descrevendo o algoritmo de animação do esqueleto conforme ele é implementado no Flame Steel Engine.
Como o algoritmo é o mais complexo de todos que implementei, podem aparecer erros nas notas sobre o processo de desenvolvimento. No artigo anterior sobre esse algoritmo, cometi um erro; o array de ossos é transferido para o shader para cada malha separadamente, e não para o modelo inteiro.
Hierarquia de nós
Para que o algoritmo funcione corretamente é necessário que o modelo contenha uma conexão entre os ossos entre si (gráfico). Vamos imaginar uma situação em que duas animações são reproduzidas simultaneamente – – pule e levante a mão direita. A animação de salto deve levantar o modelo ao longo do eixo Y, enquanto a animação de levantar o braço deve levar isso em consideração e subir com o modelo enquanto ele salta, caso contrário o braço permanecerá no lugar por conta própria.
Descreveremos a conexão dos nós para este caso – o corpo contém a mão. Ao elaborar o algoritmo, o gráfico ósseo será lido, todas as animações serão levadas em consideração com as conexões corretas. Na memória do modelo, o gráfico é armazenado separadamente de todas as animações, apenas para refletir a conectividade dos ossos do modelo.
Interpolação na CPU
No último artigo descrevi o princípio de renderização de animação esquelética – “matrizes de transformação são transferidas da CPU para o shader a cada quadro de renderização.”
Cada quadro de renderização é processado na CPU; para cada osso da malha, o mecanismo recebe a matriz de transformação final usando interpolação de posição, rotação e zoom. Durante a interpolação da matriz óssea final, uma passagem é feita através da árvore de nós para todas as animações de nós ativos, a matriz final é multiplicada pelas matrizes pai e, em seguida, enviada para renderização ao sombreador de vértice.
Os vetores são usados para interpolação de posição e a ampliação é usada para rotação, porque; eles são muito fáceis de interpolar (SLERP), ao contrário dos ângulos de Euler, e também são muito fáceis de representar como uma matriz de transformação.
Como simplificar a implementação
Para facilitar a depuração do vertex shader, adicionei uma simulação do vertex shader na CPU usando a macro FSGLOGLNEWAGERENDERER_CPU_BASED_VERTEX_MODS_ENABLED. O fabricante de placas de vídeo NVIDIA possui um utilitário para depurar código de shader Nsight, talvez ele também possa simplificar o desenvolvimento de algoritmos complexos de shader de vértices/pixels, mas nunca consegui testar sua funcionalidade. A simulação na CPU foi suficiente.
No próximo artigo pretendo descrever a mistura de múltiplas animações e preencher as lacunas restantes.
Fontes
https://www.youtube.com/watch?v= f3Cr8Yx3GGA
Adicionando suporte para scripts JavaScript em C++
Neste post descreverei uma maneira de adicionar suporte para scripts JavaScript a uma aplicação C++ usando a biblioteca Tiny-JS.
Tiny-JS é uma biblioteca para incorporação em C++, fornecendo execução de código JavaScript, com suporte para vinculações (a capacidade de chamar código C++ a partir de scripts)
No começo eu queria usar as bibliotecas populares ChaiScript, Duktape ou Connect Lua, mas devido a dependências e possíveis dificuldades de portabilidade para diferentes plataformas, decidi encontrar uma biblioteca MIT JS simples, mínima, mas poderosa; JS atende a esses critérios. A única desvantagem desta biblioteca é a falta de suporte/desenvolvimento por parte do autor, mas seu código é bastante simples, o que permite assumir o suporte se necessário.
Baixe Tiny-JS do repositório:
https://github.com/gfwilliams/tiny-js
Em seguida, adicione cabeçalhos Tiny-JS ao código responsável pelos scripts:
#include "tiny-js/TinyJS.h"
#include "tiny-js/TinyJS_Functions.h"
Adicione arquivos TinyJS .cpp ao estágio de construção e você poderá começar a escrever scripts de carregamento e execução.
Um exemplo de utilização da biblioteca está disponível no repositório:
https://github.com/gfwilliams/tiny-js/blob/master/Script.cpp
https://github.com/gfwilliams/tiny-js/blob/wiki/CodeExamples.md
Um exemplo de implementação da classe handler pode ser encontrado no projeto SpaceJaguar:
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
Exemplo de script de jogo adicionado ao aplicativo:
https://gitlab.com/demensdeum/space-jaguar-action-rpg/-/blob/master/project/resources/com.demensdeum.spacejaguaractionrpg.scripts.sceneController.js
Fontes
https://github.com/gfwilliams/tiny-js
https://github.com/dbohdan/embedded-scripting-languages
https://github.com/AlexKotik/embeddable-scripting-languages
Construindo um aplicativo C++ SDL para iOS no Linux
Nesta postagem, descreverei o procedimento para criar um aplicativo C++ SDL para iOS no Linux, assinar um arquivo ipa sem uma assinatura paga do Apple Developer e instalá-lo em um dispositivo limpo (iPad) usando macOS sem Jailbreak.< /p>
Primeiro, vamos instalar o conjunto de ferramentas de compilação para Linux:
https://github.com/tpoechtrager/cctools-port
O conjunto de ferramentas precisa ser baixado do repositório e, em seguida, siga as instruções no site do Godot Engine para concluir a instalação:
https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html
No momento, você precisa baixar o Xcode dmg e copiar o SDK de lá para construir o cctools-port. Esta etapa é mais fácil de concluir no macOS; basta copiar os arquivos SDK necessários do Xcode instalado. Após a montagem bem-sucedida, o terminal conterá o caminho para o conjunto de ferramentas do compilador cruzado.
Em seguida, você pode começar a criar o aplicativo SDL para iOS. Vamos abrir o cmake e adicionar as alterações necessárias para construir o código C++:
SET(CMAKE_SYSTEM_NAME Darwin)
SET(CMAKE_C_COMPILER arm-apple-darwin11-clang)
SET(CMAKE_CXX_COMPILER arm-apple-darwin11-clang++)
SET(CMAKE_LINKER arm-apple-darwin11-ld)
Agora você pode compilar usando cmake e make, mas não se esqueça de adicionar $PATH ao conjunto de ferramentas do compilador cruzado:
PATH=$PATH:~/Sources/cctools-port/usage_examples/ios_toolchain/target/bin
Para uma correta vinculação com frameworks e SDL, escrevemos eles em cmake, dependências do jogo Space Jaguar por exemplo:
target_link_libraries(
${FSEGT_PROJECT_NAME}
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libclang_rt.ios.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_mixer.a
${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/libSDL2_image.a
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreServices.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/ImageIO.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Metal.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AVFoundation.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/GameController.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreMotion.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreGraphics.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/AudioToolbox.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/CoreAudio.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/QuartzCore.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/OpenGLES.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/UIKit.framework"
"${FLAME_STEEL_PROJECT_ROOT_DIRECTORY}/scripts/buildScripts/ios/resources/libs/Foundation.framework"
)
No meu caso, as bibliotecas SDL, SDL_Image, SDL_mixer são compiladas no Xcode no macOS antecipadamente para vinculação estática; Frameworks copiados do Xcode. A biblioteca libclang_rt.ios.a também foi adicionada, que inclui chamadas de tempo de execução específicas do iOS, por exemplo isOSVersionAtLeast. Uma macro está incluída para trabalhar com OpenGL ES, desabilitando funções não suportadas na versão móvel, semelhante ao Android.
Depois de resolver todos os problemas de construção, você deverá obter o binário montado para arm. A seguir, vamos considerar a execução do binário montado em um dispositivo sem Jailbreak.
No macOS, instale o Xcode, cadastre-se no portal da Apple, sem pagar pelo programa de desenvolvedor. Adicione uma conta no Xcode -> Preferências -> Contas, crie um aplicativo em branco e construa em um dispositivo real. Durante a montagem, o dispositivo será adicionado à conta de desenvolvedor gratuita. Após a montagem e lançamento, você precisa construir o arquivo para fazer isso, selecione Dispositivo e produto iOS genérico -> Arquivo. Depois que o arquivo for compilado, extraia os arquivos incorporados.mobileprovision e PkgInfo dele. No log de compilação do dispositivo, encontre a linha de codesign com a chave de assinatura correta, o caminho para o arquivo de direitos com a extensão app.xcent e copie-o.
Copie a pasta .app do arquivo, substitua o binário no arquivo por um compilado por um compilador cruzado no Linux (por exemplo SpaceJaguar.app/SpaceJaguar), depois adicione os recursos necessários ao .app, verifique o integridade dos arquivos PkgInfo e incorporado.mobileprovision no .app do arquivo, copie novamente se necessário. Assinamos novamente o .app usando o comando codesign – codesign requer uma chave de entrada para assinar, o caminho para o arquivo de direitos (pode ser renomeado com uma extensão .plist)
Após assinar novamente, crie uma pasta Payload, mova a pasta com a extensão .app para lá, crie um arquivo zip com Payload na raiz, renomeie o arquivo com a extensão .ipa. Depois disso, no Xcode, abra a lista de dispositivos e arraste e solte o novo ipa na lista de aplicativos do dispositivo; A instalação via Apple Configurator 2 não funciona para este método. Se a nova assinatura for feita corretamente, o aplicativo com o novo binário será instalado em um dispositivo iOS (por exemplo iPad) com certificado de 7 dias, o que é suficiente para o período de teste.
Fontes
https://github.com/tpoechtrager/cctools-port
https://docs.godotengine.org/ru/latest/development/compiling/cross-compiling_for_ios_on_linux.html
https://jonnyzzz.com/blog/2018/06/13/link-error-3/
https://stackoverflow.com/questions/6896029/re-sign-ipa-iphone
https://developer.apple.com/library/archive/documentation/Security/Conceptual/CodeSigningGuide/Procedures/Procedures.html
Consertando um HDD lento no Windows 10
Esta nota é dedicada a todos os usuários de disco rígido que não desistem.
Após 1,5 anos usando o laptop HP Pavilion com HDD duplo (Windows 10) e SSD (Ubuntu), comecei a notar tempos de carregamento muito longos para aplicativos, uma falta de resposta geral da interface e congelamentos nas operações mais simples no Windows 10. O problema foi minimizado na medida em que foi possível usar o laptop novamente. A seguir, descreverei as etapas que executei para corrigir o problema.
Diagnóstico
Para começar a pesquisa, precisamos primeiro eliminar qualquer tipo de farsa, vamos determinar as principais causas das falhas no disco rígido. O que pode dar errado ao trabalhar com um disco rígido? Podem surgir problemas no nível físico da eletrônica e no nível lógico dos dados do software.
Problemas eletrônicos incluem coisas como: fonte de alimentação do computador/laptop que não funciona, problemas com a bateria do laptop; desgaste dos componentes do disco rígido, problemas nos circuitos e chips dos componentes internos do disco, erros de firmware, consequências de choques/quedas do disco ou problemas semelhantes com outros dispositivos que afetam seu funcionamento.
O desgaste crítico de um disco rígido é considerado o momento em que aparece um número tão grande de setores defeituosos (blocos defeituosos) que a operação posterior da unidade é impossível. Esses blocos são bloqueados pelo firmware do disco rígido, os dados são transferidos para outros setores automaticamente e não devem afetar o funcionamento do disco até um determinado momento crítico.
Problemas de lógica do programa incluem erros no sistema de arquivos devido à operação incorreta de aplicativos, ações do usuário: desligar o dispositivo enquanto está quente, concluir processos de gravação sem interromper corretamente os aplicativos, erros em drivers, serviços do sistema operacional.
Sem ferramentas especializadas de diagnóstico eletrônico, só podemos verificar a exatidão do nível de software no processo, podendo ser descobertos problemas eletrônicos, que geralmente são eliminados pelo método de reparo de bloco (substituição de componentes/chips); A seguir, consideraremos métodos de diagnóstico de software usando utilitários de diagnóstico. Vale ressaltar que todos os utilitários devem ser lançados no sistema com prioridade máxima, pois outros aplicativos podem interferir nas medições de desempenho e bloquear a leitura/gravação do disco, o que levará a resultados de diagnóstico incorretos.
INTELIGENTE
S.M.A.R.T. sistema de monitoramento de status do dispositivo de armazenamento – HDD, SDD, eMMC, etc. Permite avaliar o desgaste do dispositivo, visualizar o número de blocos defeituosos e tomar outras ações com base nos dados. Você pode visualizar o SMART em diferentes aplicativos para trabalhar com discos. Prefiro usar utilitários do fabricante; Para meu disco rígido Seagate, usei o utilitário SeaTools, para o qual o status foi exibido como BOM, ou seja, o firmware do disco pensa que está tudo bem.
Utilitários do fabricante
Os utilitários do fabricante do disco fornecem testes para verificar seu funcionamento. O SeaTools possui vários tipos de testes, você pode usar todos eles para localizar o problema. Testes rápidos e simples podem não revelar problemas, por isso prefira testes longos. No meu caso, apenas o Long Test encontrou erros.
Passeio lento
Para verificar a exatidão da leitura, encontrando blocos lentos ou mortos, escrevi um aplicativo slowride, funciona com um princípio muito simples – – abre um descritor de dispositivo de bloco, com as configurações especificadas pelo usuário, lê os dados de todo o dispositivo, com medições de tempo, saída de blocos lentos. O programa para no primeiro erro; neste caso, você terá que passar para utilitários mais sérios para remoção de dados, já que não é possível ler os dados do disco usando métodos simples.
No meu caso, a leitura de todo o disco foi realizada corretamente, com leve queda de velocidade – 90 MB/seg (5400 rpm) em um segundo, em algumas áreas do disco. Daí se poderia concluir que eu estava lidando com um problema de software.
Análise acústica
Este método não se aplica a métodos de diagnóstico de software, mas é muito importante para corrigir o problema. Por exemplo, se a fonte de alimentação estiver funcionando parcialmente, o disco rígido pode congelar/congelar e emitir um clique alto.
No meu caso, ao trabalhar com um disco no Windows 10, ouvi algo familiar para todos os proprietários de HDD, som alto de estalo da cabeça do disco indo e voltando ao tentar fazer algo no sistema operacional, mas o som era quase constante, isso me fez pensar que havia muita fragmentação disco, sobrecarga de disco com serviços em segundo plano.
Correção
Nenhum problema eletrônico foi detectado durante o diagnóstico de software; a leitura bloco por bloco de todo o disco foi concluída corretamente, mas o SeaTools mostrou erros durante o teste longo.
Utilitários do fabricante
Além do diagnóstico, o software do fabricante do disco fornece procedimentos de correção de erros. No SeaTools, o botão Corrigir tudo é responsável por isso. Após confirmar seu consentimento para a potencial perda de dados, o processo de correção será iniciado; Essa correção ajudou no meu caso? Não, o disco continuou a operar alto e lentamente, mas o Teste Longo não apresentou mais erros.
CHKDSK
CHKSDK é um utilitário da Microsoft para solucionar erros de software em sistemas de arquivos do Windows. Com o tempo, esses erros se acumulam no disco e podem interferir bastante no trabalho, inclusive levando à incapacidade de ler/gravar quaisquer dados. Você pode encontrar instruções para usar o utilitário no site da Microsoft, mas recomendo usar todos os sinalizadores possíveis para corrigir erros (no momento em que este artigo foi escrito, era /r /b /f); Você precisa executar a verificação com direitos de administrador através do terminal do Windows (cmd), para a partição do sistema ela ocorrerá na inicialização do sistema, e pode demorar muito, no meu caso demorou 12 horas.
Essa correção ajudou no meu caso? Não.
Desfragmentação de disco
Os dados no disco são processados em blocos; arquivos grandes geralmente são gravados em vários blocos/fragmentos. Com o tempo, muitos arquivos excluídos criam blocos vazios que não estão próximos, por isso, ao gravar arquivos, eles preenchem esses vazios, e a cabeça do disco tem que percorrer fisicamente longas distâncias. Esse problema é chamado de fragmentação e apenas usuários de disco rígido o enfrentam. Na época de várias correções, a fragmentação do meu disco rígido estava em 41%, visualmente ficou assim:
Ou seja, está tudo ruim. Você pode ver a fragmentação e desfragmentá-la usando o utilitário Defragger ou o desfragmentador integrado. Você também pode ativar o serviço “Otimizar unidades” no Windows 10, agende a desfragmentação no painel de controle. Apenas as unidades HDD precisam de desfragmentação; não é aconselhável habilitá-la para unidades SSD, pois isso levará ao desgaste acelerado do disco, aparentemente por esse motivo, a desfragmentação em segundo plano está desabilitada por padrão.
Uma opção alternativa de desfragmentação também é conhecida – transferir dados para outro disco, formatar o disco e copiar os dados de volta. Neste caso, os dados serão gravados em setores completamente vazios, mantendo a estrutura lógica correta para o funcionamento do sistema. Esta opção apresenta muitos problemas ao redefinir metadados potencialmente críticos que podem não ser movidos durante a cópia normal.
Desativar serviços
Usando o utilitário Process Monitor de Mark Russinovich você pode acompanhar os processos que carregam o disco rígido com seu trabalho, basta ativar as colunas IO Write/Read. Depois de pesquisar esta coluna, desativei o serviço Xbox Game Bar, o conhecido serviço de aceleração em segundo plano para programas Superfetch sob o novo nome SysMain, através do painel de serviços do painel de controle. O Superfetch deve analisar constantemente os aplicativos que o usuário usa e acelerar seu lançamento armazenando em cache na RAM, no meu caso, isso levou ao carregamento em segundo plano de todo o disco e à incapacidade de funcionar.
Limpando o disco
Também apaguei aplicativos antigos e arquivos desnecessários, liberando setores para a correta fragmentação, simplificando o funcionamento do sistema operacional, reduzindo o número de serviços e programas pesados e inúteis.
Total
O que ajudou mais? Uma diferença notável no desempenho foi alcançada após a desfragmentação do disco, os congelamentos espontâneos foram eliminados com a desativação dos serviços Xbox e Superfetch; Esses problemas não ocorreriam se eu tivesse usado um SSD? Definitivamente não haveria problemas com operação lenta devido à fragmentação, problemas com serviços teriam que ser corrigidos em qualquer caso e erros de software não dependem do tipo de unidade. Num futuro próximo estou planejando uma transição completa para SSD, mas por enquanto “Viva as panquecas, panquecas para sempre!”
Links
http://www.outsidethebox.ms/why-windows-8-defragments-your-ssd-and-how-you-can-avoid-this/
https://channel9.msdn.com/Shows/The-Defrag-Show
https://www.seagate.com/ru/ru/support/downloads/seatools/
https://www.ccleaner.com/defraggler/download
https://docs.microsoft.com/en-us/windows-server/administration/windows-commands/chkdsk
https://gitlab.com/demensdeum/slowride/
Escrevendo um servidor backend em C++ FCGI
Uma breve nota sobre como escrevi a parte do servidor para o editor 3D Cube Art Project, o servidor deve salvar e exibir o trabalho dos usuários da versão web, fornecendo-lhes URLs curtas usando o botão salvar. No começo eu queria usar Swift/PHP/Ruby/JS ou alguma linguagem moderna semelhante para o backend, mas depois de observar as características do meu VPS, decidi escrever o servidor em C/C++.
Primeiro você precisa instalar o libfcgi no servidor e o módulo de suporte fcgi para o seu servidor web, exemplo para Ubuntu e Apache:
sudo apt install libfcgi libapache2-mod-fcgid
Em seguida configuramos o módulo no config:
FcgidMaxProcessesPerClass – número máximo de processos por classe, defini como 1 processo porque não espero uma carga grande.
AddHandler fcgid-script .fcgi – extensão de arquivo com a qual o módulo fcgi deve iniciar.
Adicione à configuração a pasta a partir da qual os aplicativos cgi serão iniciados:
A seguir, escrevemos uma aplicação em C/C++ com suporte fcgi, montamos e copiamos para a pasta /var/www/html/cgi-bin.
Exemplos de código e script de construção:
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/cubeArtProjectServer.cpp
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/build.sh
Depois disso, você precisará reiniciar seu servidor web:
systemctl restart apache2
Em seguida, insira as permissões necessárias para executar a pasta cgi-bin via chmod.
Depois disso, seu programa cgi deverá funcionar através de um navegador usando o link, exemplo para o servidor Cube Art Project:
http://192.243.103.70/cgi-bin/cubeArtProject/cubeArtProjectServer.fcgi
Se algo não funcionar, consulte os logs do servidor web ou conecte-se com um depurador ao processo em execução; o processo de depuração não deve ser diferente do processo de depuração de um aplicativo cliente normal.
Fontes
https://habr.com/ru/post/154187/http://chriswu.me/blog/writing-hello-world-in-fcgi-with-c-plus-plus/
Código fonte
https://gitlab.com/demensdeum/cube-art -projeto-servidor
Portando um aplicativo C++ SDL para Android
Neste post descreverei minha experiência de portar um protótipo de editor 3D Cube Art Projectno Android.
Primeiro, vejamos o resultado; um editor com um cursor de cubo 3D vermelho está sendo executado no emulador:
Para uma montagem bem-sucedida, você deve fazer o seguinte:
- Instale o Android SDK e o NDK mais recentes (quanto mais recente a versão do NDK, melhor).
- Baixe o código-fonte do SDL2 e pegue o modelo de lá para construir o aplicativo Android.
- Adicione imagem SDL e misturador SDL à montagem.
- Adicionar as bibliotecas do meu mecanismo de jogo e kit de ferramentas, suas dependências (GLM, JSON para C++ moderno)
- Adaptar arquivos assembly para Gradle.
- Adaptar código C++ para compatibilidade com Android, alterações nos componentes dependentes da plataforma afetados (OpenGL ES, inicialização de contexto gráfico)
- Crie e teste o projeto no emulador.
Modelo de projeto
Carregando fontes SDL, SDL Image, SDL Mixer:
https://www.libsdl.org/download-2.0.php
A pasta docs contém instruções detalhadas para trabalhar com o modelo de projeto Android; copie o diretório android-project para uma pasta separada, crie um link simbólico ou copie a pasta SDL para android-project/app/jni.
Substituímos o identificador correto pelo sinalizador avd, iniciamos o emulador Android no diretório Sdk:
cd ~/Android/Sdk/emulator
./emulator -avd Pixel_2_API_24
Especifique os caminhos no script, monte o projeto:
rm -rf app/build || true
export ANDROID_HOME=/home/demensdeum/Android/Sdk/
export ANDROID_NDK_HOME=/home/demensdeum/Android/android-ndk-r21-beta2/
./gradlew clean build
./gradlew installDebug
O modelo de projeto SDL com código C do arquivo deve ser montado
android-sdl-test-app/cube-art-project-android/app/jni/src/YourSourceHere.c
Dependências
Baixe o código-fonte em arquivos para SDL_image, SDL_mixer:
https://www.libsdl.org/projects/SDL_image/
https://www.libsdl.org/projects/SDL_mixer/
Carregando as dependências do seu projeto, por exemplo minhas bibliotecas compartilhadas:
https://gitlab.com/demensdeum/FlameSteelCore/
https://gitlab.com/demensdeum/FlameSteelCommonTraits
https://gitlab.com/demensdeum/FlameSteelBattleHorn
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkit/
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/FSGL
https://gitlab.com/demensdeum/cube-art-project
Fazemos upload de tudo isso para app/jni, cada “módulo” em uma pasta separada, por exemplo app/jni/FSGL. A seguir, você tem a opção de encontrar geradores funcionais para os arquivos Application.mk e Android.mk, não os encontrei, mas talvez haja uma solução simples baseada no CMake. Siga os links e comece a se familiarizar com o formato de arquivo assembly para Android NDK:
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk
Você também deve ler sobre diferentes implementações de APP_STL no NDK:
https://developer.android.com/ndk/guides/cpp-support.html
Após a familiarização, criamos um arquivo Android.mk para cada “módulo”, seguido de um exemplo de arquivo assembly da biblioteca compartilhada Cube-Art-Project:
LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)
APP_STL := c++_static
APP_CPPFLAGS := -fexceptions
LOCAL_MODULE := CubeArtProject
LOCAL_C_INCLUDES := $(LOCAL_PATH)/src $(LOCAL_PATH)/../include $(LOCAL_PATH)/../include/FlameSteelCommonTraits/src/FlameSteelCommonTraits
LOCAL_EXPORT_C_INCLUDES = $(LOCAL_PATH)/src/
define walk
$(wildcard $(1)) $(foreach e, $(wildcard $(1)/*), $(call walk, $(e)))
endef
ALLFILES = $(call walk, $(LOCAL_PATH)/src)
FILE_LIST := $(filter %.cpp, $(ALLFILES))
$(info CubeArtProject source code files list)
$(info $(FILE_LIST))
LOCAL_SRC_FILES := $(FILE_LIST:$(LOCAL_PATH)/%=%)
LOCAL_SHARED_LIBRARIES += FlameSteelCore
LOCAL_SHARED_LIBRARIES += FlameSteelBattleHorn
LOCAL_SHARED_LIBRARIES += FlameSteelCommonTraits
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkit
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkitFSGL
LOCAL_SHARED_LIBRARIES += FSGL
LOCAL_SHARED_LIBRARIES += SDL2
LOCAL_SHARED_LIBRARIES += SDL2_image
LOCAL_LDFLAGS := -static-libstdc++
include $(BUILD_SHARED_LIBRARY)
Qualquer usuário experiente do CMake entenderá essa configuração desde as primeiras linhas, os formatos são muito semelhantes, o Android.mk não possui GLOB_RECURSIVE, então você deve procurar recursivamente os arquivos de origem usando a função walk.
Alteramos Application.mk, Android.mk para criar código C++ e não C:
APP_ABI := armeabi-v7a arm64-v8a x86 x86_64
APP_PLATFORM=android-16
APP_STL := c++_static
APP_CPPFLAGS := -fexceptions
Renomeie YourSourceHere.c -> YourSourceHere.cpp, faça grep nas entradas, altere o caminho na montagem, por exemplo:
app/jni/src/Android.mk:LOCAL_SRC_FILES := YourSourceHere.cpp
Em seguida, tente construir o projeto, se você encontrar erros do compilador sobre a ausência de cabeçalhos, verifique a exatidão dos caminhos em Android.mk; Se houver erros do vinculador como “referência indefinida”, verifique se os arquivos de código-fonte nos assemblies estão especificados corretamente. As listas podem ser rastreadas especificando $(info $(FILE_LIST)) no arquivo Android.mk; Não se esqueça do mecanismo de ligação dupla, usando módulos na chave LOCAL_SHARED_LIBRARIES e ligação correta através de LD, por exemplo para FSGL:
LOCAL_LDLIBS := -lEGL -lGLESv2
Adaptação e lançamento
Tive que mudar algumas coisas, por exemplo, remover o GLEW das compilações para iOS e Android, renomear algumas das chamadas OpenGL, adicionar o postfix EOS (glGenVertexArrays -> glGenVertexArraysOES), incluir uma macro para as funções de depuração modernas ausentes , a cereja do bolo é a inclusão implícita de cabeçalhos GLES2 indicando macro GL_GLEXT_PROTOTYPES 1:
#define GL_GLEXT_PROTOTYPES 1
#include "SDL_opengles2.h"
Também observei uma tela preta nas primeiras inicializações com um erro do tipo “E/libEGL: validar_display:255 erro 3008 (EGL_BAD_DISPLAY)”, alterei a inicialização da janela SDL, o perfil OpenGL e tudo funcionou:
SDL_DisplayMode mode;
SDL_GetDisplayMode(0,0,&mode);
int width = mode.w;
int height = mode.h;
window = SDL_CreateWindow(
title,
0,
0,
width,
height,
SDL_WINDOW_OPENGL | SDL_WINDOW_FULLSCREEN | SDL_WINDOW_RESIZABLE
);
SDL_GL_SetAttribute( SDL_GL_CONTEXT_PROFILE_MASK, SDL_GL_CONTEXT_PROFILE_ES );
No emulador, o aplicativo é instalado por padrão com o ícone SDL e o nome “Jogo”.
Só tenho que explorar a possibilidade de gerar automaticamente arquivos assembly baseados no CMake, ou migrar assemblies de todas as plataformas para Gradle; no entanto, o CMake continua sendo a escolha de fato para o desenvolvimento contínuo de C++.
Código fonte
https://gitlab.com/demensdeum/android- sdl-test-app
https://gitlab.com/demensdeum/android-sdl-test-app/tree/master/cube-art-project-android
Fontes
https://developer.android.com/ ndk/guides/cpp-support.html
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk
https://lazyfoo.net/tutorials/SDL/52_hello_mobile/android_windows/index.php
https://medium.com/androiddevelopers/getting-started-with-c-and-android-native-activities-2213b402ffff
Mundo de cabeça para baixo
Para desenvolver um novo projeto, o Cube Art Project adotou a metodologia Test Driven Development. Nesta abordagem, primeiro é implementado um teste para uma funcionalidade específica do aplicativo e, em seguida, a funcionalidade específica é implementada. Considero que a grande vantagem desta abordagem é a implementação das interfaces finais, que são o menos envolvidas possível nos detalhes de implementação, antes do início do desenvolvimento da funcionalidade. Com esta abordagem, o teste dita a implementação posterior, agregando todos os benefícios da programação contratual, quando as interfaces são contratos para uma implementação específica.
Projeto de Arte Cubo – Um editor 3D no qual o usuário constrói figuras a partir de cubos; não faz muito tempo que esse gênero era muito popular. Por se tratar de uma aplicação gráfica, resolvi adicionar testes com validação de screenshots.
Para validar as capturas de tela, você precisa obtê-las do contexto OpenGL, isso é feito usando a função glReadPixels. A descrição dos argumentos da função é simples – posição inicial, largura, altura, formato (RGB/RGBA/etc.), ponteiro para buffer de saída; qualquer pessoa que tenha trabalhado com SDL ou tenha experiência com buffers de dados em C simplesmente substituirá os argumentos necessários. Entretanto, acho necessário descrever um recurso interessante do buffer de saída glReadPixels; os pixels são armazenados nele de baixo para cima, enquanto em SDL_Surface todas as operações básicas ocorrem de cima para baixo.
Ou seja, tendo carregado uma captura de tela de referência de um arquivo png, não consegui comparar os dois buffers diretamente, pois um deles estava de cabeça para baixo.
Para inverter o buffer de saída do OpenGL, você precisa preenchê-lo subtraindo a altura da captura de tela para a coordenada Y. No entanto, vale a pena considerar que há uma chance de ultrapassar os limites do buffer se você não subtrair um durante o preenchimento, o que acontecerá. levar à corrupção da memória.
Como sempre tento usar o paradigma OOP de “programação por interfaces”, em vez do acesso direto à memória tipo C por ponteiro, quando tentei escrever dados fora do buffer, o objeto me informou sobre isso graças à validação de limites no método .
O código final para o método de obtenção de uma captura de tela no estilo de cima para baixo:
auto width = params->width;
auto height = params->height;
auto colorComponentsCount = 3;
GLubyte *bytes = (GLubyte *)malloc(colorComponentsCount * width * height);
glReadPixels(0, 0, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);
auto screenshot = make_shared(width, height);
for (auto y = 0; y < height; y++) {
for (auto x = 0; x < width; x++) {
auto byteX = x * colorComponentsCount;
auto byteIndex = byteX + (y * (width * colorComponentsCount));
auto redColorByte = bytes[byteIndex];
auto greenColorByte = bytes[byteIndex + 1];
auto blueColorByte = bytes[byteIndex + 2];
auto color = make_shared(redColorByte, greenColorByte, blueColorByte, 255);
screenshot->setColorAtXY(color, x, height - y - 1);
}
}
free(bytes);
Fontes
https://community.khronos.org/ t/glreadpixels-fliped-image/26561
https://stackoverflow.com/questions/8346115/why-are-bmps-stored-upside-down
Código fonte
https://gitlab.com/demensdeum/cube- art-project-bootstrap
Substring comum mais longa
Neste post descreverei um algoritmo para resolver o maior problema comum de substring. Digamos que estamos tentando descriptografar dados binários criptografados. Primeiro, vamos tentar encontrar padrões comuns procurando pela maior substring.
Exemplo de string de entrada:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
Estamos procurando uma string que se repete duas vezes:
CABEÇALHO DE DADOS??
Prefixos
Primeiro, vamos escrever um método para comparar os prefixos de duas strings, deixe-o retornar a string resultante na qual os caracteres do prefixo esquerdo são iguais aos caracteres do prefixo direito.
Por exemplo, para as linhas:
val lhs = "asdfWUKI"
val rhs = "asdfIKUW"
Sequência de resultados – asdf
Exemplo em Kotlin:
fun longestPrefix(lhs: String, rhs: String): String {
val maximalLength = min(lhs.length-1, rhs.length -1)
for (i in 0..maximalLength) {
val xChar = lhs.take(i)
val yChar = rhs.take(i)
if (xChar != yChar) {
return lhs.substring(0, i-1)
}
}
return lhs.substring(0,maximalLength)
}
Força Bruta
Quando as coisas não funcionam bem, você deve recorrer à força bruta. Usando o método mais longoPrefix, percorreremos a string em dois loops, o primeiro leva a string de i até o final, o segundo de i + 1 até o final, passa-os adiante para procurar o maior prefixo. A complexidade de tempo deste algoritmo é aproximadamente O(n^2) ~ O(n*^3).
Exemplo em Kotlin:
fun searchLongestRepeatedSubstring(searchString: String): String {
var longestRepeatedSubstring = ""
for (x in 0..searchString.length-1) {
val lhs = searchString.substring(x)
for (y in x+1..searchString.length-1) {
val rhs = searchString.substring(y)
val longestPrefix = longestPrefix(lhs, rhs)
if (longestRepeatedSubstring.length < longestPrefix.length) {
longestRepeatedSubstring = longestPrefix
}
}
}
return longestRepeatedSubstring
}
Matriz de sufixos
Para uma solução mais elegante, precisamos de uma ferramenta - uma estrutura de dados chamada “Suffix Array”. Esta estrutura de dados é uma matriz de substrings preenchidas em um loop, onde cada substring começa no próximo caractere da linha até o final.
Por exemplo, para a linha:
adasDATAHEADER??
A matriz de sufixos é semelhante a esta:
adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?
Resolvemos classificando
Vamos classificar o array de sufixos, depois percorrer todos os elementos em um loop onde o elemento atual está na mão esquerda (lhs), o próximo está na mão direita (rhs) e calcular o prefixo mais longo usando o longPrefix método.
Exemplo em Kotlin:
fun searchLongestRepeatedSubstring(searchString: String): String {
val suffixTree = suffixArray(searchString)
val sortedSuffixTree = suffixTree.sorted()
var longestRepeatedSubstring = ""
for (i in 0..sortedSuffixTree.count() - 2) {
val lhs = sortedSuffixTree[i]
val rhs = sortedSuffixTree[i+1]
val longestPrefix = longestPrefix(lhs, rhs)
if (longestRepeatedSubstring.length < longestPrefix.length) {
longestRepeatedSubstring = longestPrefix
}
}
return longestRepeatedSubstring
}
A complexidade de tempo do algoritmo é O(N log N), o que é muito melhor do que uma solução simples.
Fontes
https://en.wikipedia.org/wiki/Longest_common_substring_problem
Código fonte
https://gitlab.com/demensdeum/algorithms
Classificação por inserção, classificação por mesclagem
Classificação por inserção
Classificação por inserção – cada elemento é comparado com os anteriores da lista e o elemento é trocado pelo maior, se houver, caso contrário, o loop de comparação interno para. Como os elementos são classificados do primeiro ao último, cada elemento é comparado a uma lista já classificada, o que *possivelmente* reduz o tempo geral de execução. A complexidade de tempo do algoritmo é O(n^2), ou seja, idêntica à variedade da bolha.
Mesclar classificação
Mesclar classificação – a lista é dividida em grupos de um elemento, então os grupos são “mesclados” em pares com comparação simultânea. Na minha implementação, ao mesclar pares, os elementos à esquerda são comparados com os elementos à direita e, em seguida, movidos para a lista resultante; se os elementos à esquerda desaparecerem, todos os elementos à direita serão adicionados ao resultado; lista (sua comparação adicional é desnecessária, pois todos os elementos dos grupos passam por iterações de classificação)< br />O trabalho deste algoritmo é muito fácil de paralelizar; a etapa de fusão de pares pode ser realizada em threads, aguardando o término das iterações no despachante.
Saída do algoritmo para execução de thread único:
["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]
Saída do algoritmo para execução multithread:
["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]
A complexidade de tempo do algoritmo é O(n*log(n)), que é um pouco melhor que O(n^2)
Fontes
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort
Código fonte
https://gitlab.com/demensdeum /algoritmos/-/árvore/master/sortAlgoritmos/inserçãoSort
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/mergeSort
Classificação por bolha em Erlang
Bubble sort é um tanto chato, mas se torna mais interessante se você tentar implementá-lo em uma linguagem funcional para telecomunicações. Erlang.
Temos uma lista de números, precisamos classificá-la. O algoritmo de classificação por bolha percorre toda a lista, iterando e comparando os números aos pares. Durante a verificação, acontece o seguinte: um número menor é adicionado à lista de saída, ou os números são trocados na lista atual, se houver menos à direita, a pesquisa continua com o próximo número na iteração; Este percurso é repetido até que não haja mais substituições na lista.
Na prática não vale a pena utilizar devido à alta complexidade de tempo do algoritmo – O(n^2); Implementei em Erlang, no estilo imperativo, mas se tiver interesse pode procurar opções melhores:
-module(bubbleSort).
-export([main/1]).
startBubbleSort([CurrentHead|Tail]) ->
compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).
compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->
if
CurrentHead < NextHead ->
compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
true ->
compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
end;
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
if
CurrentHead < NextHead ->
OutputList = OriginalOutputList ++ [CurrentHead],
compareHeads(NextHead, Tail, OutputList, OriginalList);
true ->
OutputList = OriginalOutputList ++ [NextHead],
compareHeads(CurrentHead, Tail, OutputList, OriginalList)
end;
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
OutputList = OriginalOutputList ++ [CurrentHead],
if
OriginalList == OutputList ->
io:format("OutputList: ~w~n", [OutputList]);
true ->
startBubbleSort(OutputList)
end.
main(_) ->
UnsortedList = [69,7,4,44,2,9,10,6,26,1],
startBubbleSort(UnsortedList).
Instalação e inicialização
No Ubuntu, Erlang é muito fácil de instalar; basta digitar sudo apt install erlang no terminal. Nesta linguagem, cada arquivo deve ser um módulo, com uma lista de funções que podem ser utilizadas externamente – – exportar. Características interessantes da linguagem incluem a ausência de variáveis, apenas constantes, a ausência de uma sintaxe padrão para POO (o que não impede o uso de técnicas de POO) e, claro, cálculos paralelos sem bloqueios baseados no modelo de ator.
Você pode executar o módulo através do console erl interativo, executando um comando após o outro, ou mais simplesmente através de escript bubbleSort.erl; Para casos diferentes, o arquivo terá uma aparência diferente, por exemplo, para escript você precisa criar uma função principal a partir da qual ele será iniciado.
Fontes
https://www.erlang.org/
https://habr.com/ru/post/197364/
Código fonte
https://gitlab.com/ demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl
Algoritmo de comparação lexicográfica
O algoritmo lexicográfico de comparação de strings funciona de maneira muito simples; os códigos dos caracteres são comparados em um loop e o resultado é retornado se os caracteres não forem iguais.
Um exemplo para a linguagem C pode ser encontrado aqui:
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c
Deve-se levar em consideração que você precisa comparar caracteres em uma única codificação estática, por exemplo em Swift usei comparação caractere por caractere em UTF-32. A opção de classificação de array usando memcmp funcionará exatamente para caracteres de byte único; em outros casos (codificações de comprimento variável) a ordem pode estar incorreta. Não descarto a possibilidade de implementação baseada em codificações de comprimento variável, mas provavelmente será uma ordem de magnitude mais complicada.
A complexidade de tempo do algoritmo é O(1) no melhor caso, O(n) no médio e no pior caso
Fontes
https://ru.wikipedia.org/wiki/Lexicographic_order
Fontes
https://gitlab.com/demensdeum /algoritmos/blob/master/lexiCompare/lexiCompare.swift
Pesquisa binária
Suponha que precisamos descobrir se o endereço de e-mail “demensdeum@gmail.com” está incluído na lista de endereços de e-mail permitidos para recebimento de cartas .
Vamos percorrer toda a lista do primeiro ao último elemento, verificando se o elemento é igual ao endereço especificado – Vamos implementar um algoritmo de busca linear. Mas isso vai demorar muito ou não?
Para responder a esta pergunta, use a notação “Complexidade de tempo dos algoritmos”, “O”. O tempo de operação da busca linear no pior caso é igual ao enésimo número de elementos do array, vamos escrever isso na notação “O” – Sobre). A seguir, precisamos explicar que para qualquer algoritmo conhecido existem três indicadores de desempenho – tempos de execução do melhor caso, do pior caso e do caso médio. Por exemplo, o endereço de e-mail “demensdeum@gmail.com” está no primeiro índice do array, então ele será encontrado na primeira etapa do do algoritmo, segue-se que o tempo de execução é, na melhor das hipóteses, – O(1); e se estiver no final da lista, então este é o pior caso – Sobre(n)
Mas e os detalhes de implementação de software e desempenho de hardware, eles devem influenciar o grande O? Agora respire fundo e imagine que o cálculo da complexidade do tempo é calculado para alguma máquina abstrata ideal, na qual existe apenas esse algoritmo e nada mais.
Algoritmo
Ok, acontece que a pesquisa linear é bastante lenta, vamos tentar usar a pesquisa binária. Para começar, deve-se esclarecer que não trabalharemos com dados binários; este nome foi dado a este método devido às peculiaridades de seu trabalho. Inicialmente classificamos o array em ordem lexicográfica, então o algoritmo pega o intervalo de todo o array, obtém o elemento do meio do intervalo, compara-o lexicograficamente, e dependendo do resultado da comparação, decide qual intervalo usar para pesquisas adicionais – a metade superior da corrente ou a parte inferior. Ou seja, a cada etapa da pesquisa é tomada uma decisão a partir de dois – lógica binária. Esta etapa é repetida até que a palavra seja encontrada ou não seja encontrada (ocorre a intersecção dos índices inferior e superior do intervalo).
Desempenho deste algoritmo – o melhor caso é quando um elemento é imediatamente encontrado no meio do array O(1), o pior caso de enumeração é O(log n)
Armadilhas
Ao implementar a pesquisa binária, não apenas encontrei o interessante problema da falta de padronização da comparação lexicográfica em bibliotecas de linguagens de programação, mas também descobri a ausência de um padrão unificado para implementação localeCompare em JavaScript. O padrão ECMAScript permite diferentes implementações desta função, e é por isso que ao classificar usando localeCompare, resultados completamente diferentes podem ser observados em diferentes motores JavaScript.
Portanto, para que o algoritmo funcione corretamente, é necessário classificar e usar apenas o mesmo algoritmo de comparação lexicográfica, caso contrário nada funcionará. Co-mas se, por exemplo, você tentar classificar um array no Scala e pesquisar usando nodejs, sem implementar sua própria classificação/classificação de uma implementação, nada o aguardará, exceto decepção com a humanidade.
Fontes
O que é comparação lexicográfica e o que ela representa?
Почему для вычисления сложности алгоритмов используется log N вместо lb N?
Двоичный поиск
Знай сложности алгоритмов
https://stackoverflow.com/questions/52941016/sorting-in-localecompare-in-javascript
Código fonte
https://gitlab.com/demensdeum/algorithms
Fachada padrão
Fachada refere-se a padrões de projeto estrutural. Ele fornece uma interface única que permite trabalhar com sistemas complexos, permitindo que os clientes não tenham detalhes de implementação desses sistemas, simplificando assim seu código e implementando acoplamento fraco entre clientes e sistemas de nível inferior. GoF tem um bom exemplo de Fachada – um compilador de linguagem de programação que fornece a diferentes clientes que buscam objetivos diferentes a capacidade de montar código por meio de uma única interface de fachada do compilador.
Fontes
https://refactoring.guru/ru/design-patterns/facade
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612
Padrão abstrato de fábrica
Fábrica abstrata– fornece uma interface para criar objetos relacionados, sem especificar classes específicas.
Gosto muito do nome alternativo para esse padrão – Kit (Kit)
É muito semelhante ao Factory Method, porém, Abstract Factoriesdeve descrever o relacionamento entre os objetos que estão sendo criados, caso contrário é simplesmente um God Object o antipadrão que cria tudo é aleatório.
Imagine desenvolver um framework AR para óculos; exibimos na tela setas de navegação internas, ícones de lojas, locais interessantes, janelas e botões com informações sobre qualquer local onde o usuário esteja atualmente.
Ao mesmo tempo, precisamos da capacidade de personalizar a aparência e o comportamento dos controles do ambiente de AR. É justamente para este caso que você precisa utilizar o padrão Set.
Vamos escrever a interface de Abstract Factory e Abstract Products – protocolos pai, elementos do ambiente AR:
protocol ARFactory {
func arrow() -> ARArrow
func icon() -> ARIcon
func button() -> ARButton
func window() -> ARWindow
}
protocol ARArrow {
var image: { get }
func handleSelection()
}
protocol ARIcon {
var image: { get }
var title: String
}
protocol ARButton {
var title: String
func handleSelection()
}
protocol ARWindow {
var title: String
var draw(canvas: Canvas)
}
Agora os desenvolvedores do kit precisarão implementar um Concrete Factory baseado na interface Abstract Factory, e terão que implementar todos os elementos juntos, o resto do aplicativo será capaz de trabalhar com a fábrica sem alterar seu código.< /p>
Fontes
https://refactoring.guru/ru/design-patterns /fábrica abstrata
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612
Método de fábrica
O padrão Factory Method refere-se a padrões de design generativos.
Este padrão descreve a criação de uma interface para criar um objeto de uma classe específica. Parece simples, certo?
Em teoria
Suponha que estejamos desenvolvendo um framework para trabalhar com óculos AR, ao inclinar a cabeça para o lado, um menu de aplicativos disponíveis deverá aparecer diante dos olhos do usuário. As aplicações serão desenvolvidas por empresas terceirizadas, clientes do nosso framework. Naturalmente, não sabemos quais aplicativos, ícones, nomes devem aparecer, por isso devemos fornecer uma interface para implementar o ícone e informações relacionadas sobre o aplicativo. Vamos chamá-lo de Produto:
protocol Product {
var name: String { get }
var image: Image { get }
var executablePath: String { get }
}
Em seguida, precisamos fornecer uma interface para que nossos clientes possam implementar a emissão de uma série de aplicações para seu Produto Específico – uma série de ícones de aplicativos com nomes, que já desenharemos no framework.
Vamos escrever esta interface – Interface Creator contendo um Método de fábrica que retorna uma matriz de Produtos.
protocol Creator {
func factoryMethod() -> [Product]
}
Na prática
O primeiro cliente do nosso framework AR foi a empresa 7B – fornecedor líder de software para cafeteiras em Honduras. Eles querem vender óculos de realidade aumentada com a capacidade de preparar café, verificar se a água/grãos estão cheios e mostrar o caminho até a cafeteira mais próxima usando o modo de mapa interno.
Eles realizam o desenvolvimento do software; apenas somos obrigados a fornecer documentação sobre as interfaces do Criador e do Produto para a correta exibição da lista de aplicativos e seus posteriores. lançamento.
Após a transferência da documentação, a empresa 7B, através da interface Criador , implementa o Criador Específico – classe que retorna uma matriz de ícones de aplicativos. Os próprios aplicativos de ícone são classes de Produto Específico que implementam a interface do Produto.
Código de exemplo para produtos específicos:
class CoffeeMachineLocator: implements Product {
let name = “7B Coffee Machine Locator v.3000”
let image = Image.atPath(“images/locator.tga”)
let executablePath = “CoffeeMachineLocator.wasm”
}
class iPuchinno: implements Product {
let name = “iPuchinno 1.0.3”
let image = Image.atPath(“images/puchino.pvrtc”)
let executablePath = “neutron/ipuchBugFixFinalNoFreezeFixAlpha4.js”
}
Classe Concrete Creator, fornecendo um conjunto de duas aplicações:
class 7BAppsCreator: implements Creator {
func factoryMethod() -> [Product] {
return [CoffeeMachineLocator(), iPuchinno()]
}
}
Depois disso, a empresa 7B compila a biblioteca de Produtos Concretos, Concrete Creator e a combina com nossa estrutura, começa a vender óculos AR para suas cafeteiras, adições de nossa parte não são necessárias.
Fontes
https://refactoring.guru/ru/design-patterns/command
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612
Comando Padrão
Padrão de comando refere-se a padrões de design comportamentais.
Esse é o padrão que estou preso há muito tempo, é tão simples que é muito complexo. Mas, pessoalmente, acho que a beleza do auto-estudo é que você tem todo o tempo do mundo para pesquisar um determinado tópico de todos os ângulos.
Portanto, no GoF a aplicabilidade é descrita de forma bastante sucinta e clara:
Encapsula uma solicitação como um objeto, permitindo parametrizar clientes com diferentes solicitações, usar filas, registrar solicitações e realizar operações de cancelamento.
Agora vamos implementar uma versão simples do comando da descrição:
string fakeTrumpsRequest = “SELECT * from Users where name beginsWith DonaldTrump”
Encapsulamos a solicitação em um objeto de classe string, ele pode ser usado para configurar clientes, adicionar comandos à fila, registrar, cancelar (usando o padrão “Snapshot”)
Parece-me que isso é suficiente para realizar consultas SQL e similares, mas há detalhes de implementação, diferentes opções de aplicação, a base de código do padrão, funções de cliente e classes auxiliares também são muito diferentes.
Partes materiais
O padrão
Command começa com um protocolo Command, que contém um único método execute(). Em seguida vem o Comando e Receptor Específicos. O CC implementa a operação no Receptor, descreve a conexão entre o Receptor e a ação. Alguma coisa não está clara? Eu também, mas vamos em frente. O Clientecria uma instância de um Comando Específico, associando-o ao Receptor. Invocador – objeto que realiza o processo de lançamento de Comandos.
Agora vamos tentar descobrir usando um exemplo, digamos que queremos atualizar o myOS no myPhone, para isso iniciamos o aplicativo myOS_Update, nele pressionamos o botão Atualizar Agora! relatar uma atualização bem-sucedida.
O cliente no exemplo acima é o aplicativo myOS_Update, o Invoker é o botão “Atualizar agora!” b>atualizar o sistema utilizando o método execute(), que acessa o Receptor– daemon de atualização do sistema operacional.
Usar exemplo
Vamos aceitar a UI do aplicativo myOS_Update! tão bom que decidiram vendê-lo como um produto separado para fornecer uma interface para atualização de outros sistemas operacionais. Neste caso implementaremos uma aplicação com suporte a extensões através de bibliotecas, nas bibliotecas haverá implementações de Comandos Específicos, Receptores, deixaremos o Invoker estático/imutável , Cliente, protocolo Comandos.
Assim, não há necessidade de suporte a código mutável, pois nosso código permanecerá inalterado, problemas poderão surgir apenas quando implementado no lado do cliente, devido a erros no código de seus Comandos Específicos e Receptores. Além disso, nesta implementação não há necessidade de transferir o código fonte da aplicação principal, ou seja, encapsulamos comandos e interações UI usando o padrão Command.
Fontes
https://refactoring.guru/ru/design-patterns/command
https://www.amazon.com/Design-Patterns-Elements-Reusable-Object-Oriented/dp/0201633612
Construindo aplicativos macOS para Ubuntu OSXCross CMake
Neste post, descreverei a criação de aplicativos C++ multiplataforma para macOS em uma máquina de compilação Ubuntu usando CMake e osxcross.
Primeiro, instale o conjunto de ferramentas osxcross:
https://github.com/tpoechtrager/osxcross
A instalação ocorre em 3 etapas, baixando as dependências:
cd tools
./get_dependencies.sh
Baixe o XCode.xip do site oficial da Apple e, em seguida, baixe o SDK do XCode:
./gen_sdk_package_pbzx.sh /media/demensdeum/2CE62A79E62A4404/LinuxSupportStorage/xcode111.xip
Espero que você tenha lido o contrato de licença do XCode na última etapa. Em seguida, construa o conjunto de ferramentas com o prefixo necessário:
INSTALLPREFIX=/home/demensdeum/Apps/osxcross ./build.sh
Agora você pode usar osxcross do diretório de prefixos da etapa anterior. Vamos adicionar uma nova macro de build para o CMake, escreva tudo o que for necessário:
if (OSXCROSS)
SET(CMAKE_SYSTEM_NAME Darwin)
SET(CMAKE_C_COMPILER o64-clang)
SET(CMAKE_CXX_COMPILER o64-clang++)
SET(CMAKE_C_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_CXX_COMPILER_AR x86_64-apple-darwin19-ar)
SET(CMAKE_LINKER x86_64-apple-darwin19-ld)
SET(ENV{OSXCROSS_MP_INC} 1)
endif()
A vinculação dinâmica não foi bem-sucedida para mim, então exportamos as bibliotecas estaticamente:
if (OSXCROSS)
add_library(FlameSteelCore STATIC ${SOURCE_FILES})
else()
Em seguida, você pode se deparar com o fato de não ter as bibliotecas necessárias para o osxcross. Encontrei isso ao usar o SDL2. osxcross oferece suporte a pacotes de bibliotecas prontos – macports. Por exemplo, instalando o mixer SDL2:
osxcross-macports -v install libsdl2_mixer
Depois disso, você pode começar a construir bibliotecas/aplicativos normalmente no link cmake-make, não se esqueça de especificar a vinculação estática de bibliotecas, se necessário.
Montagem manual de bibliotecas
Atualmente, encontrei o problema de arquivamento incorreto de bibliotecas durante a vinculação estática ao construir o aplicativo final e recebo o erro:
;
file was built for archive which is not the architecture being linked (x86_64)
Muito semelhante a este ticket, conseguimos implementar um solução alternativa como resultado, o que resulta na conclusão correta da montagem. Vamos descompactar a biblioteca estática e construí-la novamente usando o arquivador osxcross:
ar x ../libFlameSteelCore.a
rm ../libFlameSteelCore.a
x86_64-apple-darwin19-ar rcs ../libFlameSteelCore.a *.o
Eu também considero pessoalmente que um dos problemas é a falta de capacidade de executar aplicativos macOS diretamente no Ubuntu (pelo menos com algumas funcionalidades), é claro que existe um projeto querido, mas o suporte ainda deixa muito a desejar.
Fontes
https://github.com/tpoechtrager/osxcross
.gif)
