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:

  1. Use o acesso aos recursos de um arquivo apk usando o AssetManager
  2. Baixe recursos da Internet e descompacte-os no diretório do aplicativo, use-os usando métodos C++ padrão
  3. 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

Visão de Jogos #4

A quarta edição de uma coluna muito inconsistente sobre os jogos da Games Vision.

World Of Horror (plataforma cruzada, panstasz) – jogo roguelike de acesso antecipado no estilo, uh, o quê? Aventura de terror em texto com elementos de RPG? Graficamente reminiscente dos jogos dos anos 80, você pode escolher entre uma paleta de 1 ou 2 bits com variações.

Os controles parecem estranhos no início, mas com o tempo você se acostuma, porque é por isso que é um roguelike – surpreender e ser original em todos os aspectos. Música chiptune incrível, estética japonesa do final dos anos 80, visuais inspirados no trabalho de Junji Ito, histórias estranhas no estilo Lovecraft, repetibilidade quase infinita.
O que mais você precisa?
Avaliação: 9/10

Castelo Eterno [REMASTERED] (PC, Daniele Vicinanzo, Giulio Perrone, Leonard Menchiari) & #8211; um jogo moderno no estilo de Outro Mundo, Flashback. A paleta foi especialmente reduzida para cores CGA. A descrição deste jogo deve começar com a lenda de sua criação: por volta de 1987, um dos filhos dos desenvolvedores do Castelo Eterno viu o jogo e se lembrou dele para o resto da vida. Como resultado, o jogo nunca foi lançado, mas. o código-fonte foi encontrado e restaurado em 2019, lançando uma versão melhorada. Porém, a descrição no Steam contém a informação de que se trata de uma remasterização de um best-seller de 1987, mas naquele ano não foi lançado um jogo com esse nome, o que é verdade e o que não é cabe a você decidir.

Os gráficos e a jogabilidade são claramente adaptados para quem gosta de sentir saudades dos bons e velhos tempos, muitas vezes há momentos em que parece que o jogo congelou, mas na verdade basta pressionar os botões de movimento ou ação para ver o que acontece; está acontecendo na tela. Esse truque cria uma sensação de estranheza e perda de controle que era frequentemente usada em jogos mais antigos, mas que foi completamente abandonada nos jogos modernos.
Avaliação: 8/10

Morte e morte Impostos (PC, Placeholder Gameworks) – Você já sonhou em trabalhar como juiz e carrasco? Você gosta de longas vestes pretas, tranças de metal e estalar os dedos? Então este é o jogo perfeito para você porque “As únicas duas coisas que você não pode evitar são a morte e os impostos.”

Este é um simulador único do anjo da morte, você tem que escolher quem vive e quem morre. Além de matar ou dar vida, você pode ler o feed de notícias no seu smartphone e ver como sua escolha afeta o mundo terrestre. Você também precisa se comunicar com seu chefe imediato chamado Faith (Fate), comprar itens e todo tipo de utensílios para a mesa, por exemplo, comprei um cacto brutal. Não se esqueça de falar com o espelho, é muito emocionante. Entre as desvantagens, vale destacar a intimidade geral do que está acontecendo, depois de alguns dias de jogo, o jogo fica um pouco monótono.
Avaliação: 8/10

Consertando um HDD lento no Windows 10

Esta nota é dedicada a todos os usuários de disco rígido que não desistem.


Original (Mae Mu)

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/

Benchmark Slowride de dispositivos de bloco

Passeio lento – utilitário para verificar a velocidade de leitura de dispositivos de bloco para sistemas operacionais compatíveis com POSIX com acesso root a /dev/sd*. Você pode testar o desempenho de leitura de dispositivos de bloco usando um limite de tempo para diagnosticar o desempenho de leitura.
Comando para ler blocos de 100 MB em todo o dispositivo, gerando blocos acima do limite de 2 segundos:

sudo ./slowride /dev/sda 100 2000

Código fonte

https://gitlab.com/demensdeum/slowride

RPG de ação 3D do Jaguar Espacial

Faz muito tempo que não anuncio novos projetos) O próximo projeto em que estou começando a trabalhar – RPG de ação 3D chamado Space Jaguar Uma história em cenário de ficção científica sobre um cara durão chamado Jag e sua difícil aventura em busca de seu pai desaparecido. Haverá gráficos 3D no Flame Steel Engine (ou possivelmente em qualquer outro popular), utilizando desenvolvimentos de projetos anteriores (Death Mask, Cube Art Project), um enredo de comédia com muitas referências, batalhas arcade e chefes. Não estou pronto para falar sobre a data de lançamento da versão completa; pretendo lançar o jogo em partes.

Repositório do projeto:
https://gitlab.com/demensdeum/space-jaguar-action-rpg

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

Projeto de Arte Cubo

Projeto de Arte Cubo – editor 3D cúbico.
Você tem uma oportunidade incrível de se mover pelo palco, construir e deletar cubos usando os botões WSAD + E, girar a roda do mouse para mudar a cor do cubo. Atualmente, apenas 16 cores são suportadas, mas muitas melhorias estão planejadas para o futuro.

Versão Web
https://demensdeum.com/games/CubeArtProjectWEB/

Windows
https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProjectWin32.zip

macOS
https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProjectMacOS.zip

Linux (x86-64)
https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProjectLinux86_64.zip

Android
(Conceito, requer mouse USB)
https://demensdeum.com/games/CubeArtProjectReleases/CubeArtProject.apk

Código fonte
https://gitlab.com/demensdeum/cube-art-project-bootstrap
https://gitlab.com/demensdeum/cube-art-project-server

Tecnologias: SDL, Emscript, MinGW, Glew, GLM, Cpp-JSON

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:

  1. Instale o Android SDK e o NDK mais recentes (quanto mais recente a versão do NDK, melhor).
  2. Baixe o código-fonte do SDL2 e pegue o modelo de lá para construir o aplicativo Android.
  3. Adicione imagem SDL e misturador SDL à montagem.
  4. Adicionar as bibliotecas do meu mecanismo de jogo e kit de ferramentas, suas dependências (GLM, JSON para C++ moderno)
  5. Adaptar arquivos assembly para Gradle.
  6. Adaptar código C++ para compatibilidade com Android, alterações nos componentes dependentes da plataforma afetados (OpenGL ES, inicialização de contexto gráfico)
  7. 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

Site da LazyFoo Productions

Talvez valha a pena mencionar o site de onde quase sempre começam meus projetos e novos desenvolvimentos, este é o site da LazyFoo Productions, onde você pode encontrar respostas para tópicos bastante hardcore: exemplos de uso de APIs complexas, aprender como combinar aparentemente incompatíveis sistemas (Android/C++) com uma explicação detalhada dos princípios de operação, exemplos de código de trabalho.

https://lazyfoo.net/

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

Desenvolvimento de jogos para ZX Spectrum em C

Esse post bobo é dedicado ao desenvolvimento de um jogo para o antigo computador ZX Spectrum em C. Vamos dar uma olhada no bonitão:

Iniciou a produção em 1982 e foi produzido até 1992. Características técnicas da máquina: processador Z80 de 8 bits, 16-128kb de memória e outras extensões, como o chip de som AY-3-8910.

Como parte da competição Yandex Retro Games Battle 2019 para esta máquina, escrevi um jogo chamado Interceptor 2020. Como não tive tempo de aprender linguagem assembly para o Z80, resolvi desenvolvê-lo em C. Como conjunto de ferramentas, escolhi um conjunto pronto – z88dk, que contém compiladores C e diversas bibliotecas auxiliares para agilizar a implementação de aplicações para o Spectrum. Ele também suporta muitas outras máquinas Z80, como MSX e calculadoras Texas Instruments.

A seguir, descreverei meu voo superficial sobre a arquitetura do computador, o conjunto de ferramentas z88dk, e mostrarei como consegui implementar a abordagem OOP e usar padrões de design.

Recursos de instalação

A instalação do z88dk deve ser realizada de acordo com o manual do repositório, porém, para usuários do Ubuntu, gostaria de destacar um recurso – Se você já possui compiladores para Z80 instalados a partir de pacotes deb, então você deve removê-los, já que z88dk os acessará da pasta bin por padrão devido à incompatibilidade das versões do compilador do conjunto de ferramentas, você provavelmente não conseguirá compilar nada.< /p>

Olá, mundo

Escrever Hello World é muito fácil:

#include 

void main()
{
    printf("Hello World");
}

É ainda mais fácil compilar um arquivo tap:

zcc +zx -lndos -create-app -o helloworld helloworld.c

Para rodar, use qualquer emulador ZX Spectrum com suporte a arquivo tap, por exemplo online:
http://jsspeccy.zxdemo.org/

Desenhe na imagem em tela cheia

tl;dr As imagens são desenhadas em blocos, blocos de tamanho 8×8 pixels, os próprios blocos são incorporados na fonte Spectrum e, em seguida, a imagem é impressa como uma linha a partir dos índices.

A biblioteca de saída de sprites e blocos sp1 produz blocos usando UDG. A imagem é traduzida em um conjunto de UDGs (blocos) individuais e depois montados na tela usando índices. Deve ser lembrado que UDG é usado para exibir texto, e se sua imagem contiver um conjunto muito grande de blocos (por exemplo, mais de 128 blocos), você terá que ir além dos limites do conjunto e apagar o Spectrum padrão fonte. Para contornar essa limitação, utilizei uma base de 128 – 255 simplificando as imagens, deixando a fonte original no lugar. Sobre simplificar as imagens abaixo.

Para desenhar imagens em tela cheia você precisa se munir de três utilitários:
Gimp
img2spec
png2c-z88dk

Existe uma maneira para verdadeiros homens ZX, verdadeiros guerreiros retrô, é abrir um editor gráfico usando a paleta Spectrum, conhecendo os recursos de saída da imagem, prepará-la manualmente e carregá-la usando png2c-z88dk ou png2scr.< /p>

A maneira mais fácil – pegue uma imagem de 32 bits, mude o número de cores para 3-4 no Gimp, edite-a levemente e importe-a para img2spec para não trabalhar com restrições de cores manualmente, exporte png e converta-a em um array C usando png2c- z88dk.

Lembre-se de que, para uma exportação bem-sucedida, cada bloco não pode conter mais de duas cores.

Como resultado, você receberá um arquivo h que contém o número de blocos únicos, se houver mais de ~128, simplifique a imagem no Gimp (aumente a repetibilidade) e execute o procedimento de exportação sobre um novo .

Após a exportação, você literalmente carrega a “fonte” dos blocos e imprime o “texto” dos índices dos blocos na tela. Abaixo está um exemplo da “classe” de renderização:

// грузим шрифт в память
    unsigned char *pt = fullscreenImage->tiles;

    for (i = 0; i < fullscreenImage->tilesLength; i++, pt += 8) {
            sp1_TileEntry(fullscreenImage->tilesBase + i, pt);
    }

    // ставим курсор в 0,0
    sp1_SetPrintPos(&ps0, 0, 0);

    // печатаем строку
    sp1_PrintString(&ps0, fullscreenImage->ptiles);

Desenhando sprites na tela

A seguir descreverei um método para desenhar sprites de 16×16 pixels na tela. Não cheguei na animação e na mudança de cores, porque… É trivial que já nesta fase, presumo, tenha ficado sem memória. Portanto, o jogo contém apenas sprites monocromáticos transparentes.

Desenhamos uma imagem png monocromática 16×16 no Gimp, depois usando png2sp1sprite a traduzimos em um arquivo assembly asm, em código C declaramos arrays do arquivo assembly e adicionamos o arquivo na fase de montagem.< /p>

Após a etapa de declaração do recurso sprite, ele deve ser adicionado na tela na posição desejada, segue abaixo um exemplo do código da “classe” do objeto do jogo:

    struct sp1_ss *bubble_sprite = sp1_CreateSpr(SP1_DRAW_MASK2LB, SP1_TYPE_2BYTE, 3, 0, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2,    SP1_TYPE_2BYTE, col2-col1, 0);
    sp1_AddColSpr(bubble_sprite, SP1_DRAW_MASK2RB,  SP1_TYPE_2BYTE, 0, 0);
    sp1_IterateSprChar(bubble_sprite, initialiseColour);

A partir dos nomes das funções você pode entender aproximadamente o significado de – aloque memória para o sprite, adicione duas colunas 8×8, adicione uma cor para o sprite.

A posição do sprite é indicada em cada quadro:

sp1_MoveSprPix(gameObject->gameObjectSprite, Renderer_fullScreenRect, gameObject->sprite_col, gameObject->x, gameObject->y);

Emulando OOP

Não existe sintaxe para OOP em C. O que você deve fazer se ainda quiser? Você precisa conectar sua mente e ser iluminado pela ideia de que não existe equipamento OOP; em última análise, tudo se resume a uma das arquiteturas de máquina, na qual simplesmente não existe o conceito de objeto e outras abstrações associadas a ele.< /p>

Esse fato me impediu por muito tempo de entender por que OOP é necessário, por que é necessário usá-lo se no final tudo se trata de código de máquina.

Porém, após trabalhar no desenvolvimento de produtos, descobri as delícias desse paradigma de programação, principalmente, é claro, flexibilidade de desenvolvimento, mecanismos de proteção de código, com abordagem correta, reduzindo entropia, simplificando o trabalho em equipe. Todos os benefícios acima decorrem de três pilares – polimorfismo, encapsulamento, herança.

Vale ressaltar também a simplificação da resolução de questões relacionadas à arquitetura de aplicações, pois 80% dos problemas de arquitetura foram resolvidos por cientistas da computação no século passado e descritos na literatura sobre padrões de projeto. A seguir, descreverei maneiras de adicionar sintaxe semelhante a OOP em C.

É mais conveniente tomar estruturas C como base para armazenar dados de uma instância de classe. Claro, você pode usar um buffer de bytes, criar sua própria estrutura para classes, métodos, mas por que reinventar a roda? Afinal, já estamos reinventando a sintaxe.

Dados da turma

Exemplo de campos de dados de “classe” do GameObject:

struct GameObjectStruct {
    struct sp1_ss *gameObjectSprite;
    unsigned char *sprite_col;
    unsigned char x;
    unsigned char y;
    unsigned char referenceCount;
    unsigned char beforeHideX;
    unsigned char beforeHideY;
};
typedef struct GameObjectStruct GameObject;

Salve nossa classe como “GameObject.h”, faça #include “GameObject.h” no lugar certo e use-a.

Métodos de classe

Levando em consideração a experiência dos desenvolvedores da linguagem Objective-C, a assinatura de um método de classe serão funções em escopo global, o primeiro argumento será sempre a estrutura de dados, seguido dos argumentos do método. Abaixo está um exemplo de “método” da “classe” GameObject:

void GameObject_hide(GameObject *gameObject) {
    gameObject->beforeHideX = gameObject->x;
    gameObject->beforeHideY = gameObject->y;
    gameObject->y = 200;
}

A chamada do método é semelhante a esta:

GameObject_hide(gameObject);

Construtores e destruidores são implementados da mesma maneira. É possível implementar um construtor como alocador e inicializador de campo, mas prefiro controlar a alocação e inicialização de objetos separadamente.

Trabalhando com memória

Gerenciamento manual de memória do formulário usando malloc e free agrupados em macros novas e de exclusão para corresponder ao C++:

#define new(X) (X*)malloc(sizeof(X))
#define delete(X) free(X)

Para objetos que são usados ​​por várias classes ao mesmo tempo, o gerenciamento de memória semi-manual é implementado com base na contagem de referências, à imagem e semelhança do antigo mecanismo ARC do Objective-C Runtime:

void GameObject_retain(GameObject *gameObject) {
    gameObject->referenceCount++;
}

void GameObject_release(GameObject *gameObject) {
    gameObject->referenceCount--;

    if (gameObject->referenceCount < 1) { sp1_MoveSprAbs(gameObject->gameObjectSprite, &Renderer_fullScreenRect, NULL, 0, 34, 0, 0);
        sp1_DeleteSpr(gameObject->gameObjectSprite);
        delete(gameObject);
    }
}

Assim, cada classe deve declarar o uso de um objeto compartilhado usando reter, liberando propriedade por meio de release. A versão moderna do ARC usa chamadas automáticas de retenção/liberação.

Som!

O Spectrum possui um tweeter capaz de reproduzir música de 1 bit; os compositores da época conseguiam reproduzir nele até 4 canais de som simultaneamente.

O Spectrum 128k contém um chip de som separado AY-3-8910, que pode reproduzir música rastreada.

Uma biblioteca é oferecida para usar o tweeter no z88dk

O que resta aprender

Eu estava interessado em conhecer o Spectrum, implementar o jogo usando o z88dk e aprender muitas coisas interessantes. Ainda tenho muito que aprender, por exemplo, o montador Z80, pois ele me permite usar toda a potência do Spectrum, trabalhar com bancos de memória e trabalhar com o chip de som AY-3-8910. Espero participar da competição no próximo ano!

Links

https://rgb.yandex
https://vk.com/sinc_lair
https://www.z88dk.org/forum/

Código fonte

https://gitlab.com/demensdeum/ zx-projects/tree/master/interceptor2020

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

Construa para Windows no Ubuntu MinGW CMake

Neste post descreverei o processo de construção de bibliotecas e aplicativos para Windows usando o conjunto de ferramentas MinGW32 no Ubuntu.
Instale o vinho, mingw:

sudo apt-get install wine mingw-w64

Depois disso, você já pode criar aplicativos C/C++ para Windows:

# C
i686-w64-mingw32-gcc helloWorld.c -o helloWorld32.exe      # 32-bit
x86_64-w64-mingw32-gcc helloWorld.c -o helloWorld64.exe    # 64-bit
 
# C++
i686-w64-mingw32-g++ helloWorld.cc -o helloWorld32.exe     # 32-bit
x86_64-w64-mingw32-g++ helloWorld.cc -o helloWorld64.exe   # 64-bit

O exe coletado pode ser verificado usando wine.

A seguir, veremos as alterações na compilação do CMake, o arquivo CMakeLists.txt, adicionando coisas específicas do MinGW ao arquivo de compilação:

if (MINGW32)
set(CMAKE_SYSTEM_NAME Windows)
SET(CMAKE_C_COMPILER i686-w64-mingw32-gcc)
SET(CMAKE_CXX_COMPILER i686-w64-mingw32-g++)
SET(CMAKE_RC_COMPILER i686-w64-mingw32-windres)
set(CMAKE_RANLIB i686-w64-mingw32-ranlib)
endif()

// для сборки shared dll
elseif (MINGW32)
add_library(FlameSteelEngineGameToolkit.dll SHARED ${SOURCE_FILES})
else()

// обязательно линкуем со всеми зависимостями
if (MINGW32)
target_link_libraries(
                        FlameSteelEngineGameToolkit.dll 
                        -static-libgcc
                        -static-libstdc++
                        SDL2 
                        SDL2_mixer 
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCore/FlameSteelCore.dll
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelBattleHorn/FlameSteelBattleHorn.dll
                        /home/demensdeum/Sources/cube-art-project-bootstrap/FlameSteelFramework/FlameSteelCommonTraits/FlameSteelCommonTraits.dll)

set_target_properties(FlameSteelEngineGameToolkit.dll PROPERTIES
        PREFIX ""
        SUFFIX ""
        LINK_FLAGS "-Wl,--add-stdcall-alias"
        POSITION_INDEPENDENT_CODE 0 # this is to avoid MinGW warning; 
        # MinGW generates position-independent-code for DLL by default
)
else()

Coleta:

cmake -DMINGW32=1 .
make

A saída será uma dll ou exe, dependendo do que você está coletando. Para um exemplo prático, você pode dar uma olhada no repositório do novo Cube-Art-Project e suas bibliotecas:
https://gitlab.com/demensdeum/cube-art-project
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/cube-art-project-bootstrap

Fontes
https://arrayfire.com/cross-compile-to-windows-from-linux/

Autoteste simples de Emscripten para ChromeDriver

Nesta nota, descreverei a implementação da execução de um autoteste para o ChromeDriver do navegador Chrome, que executa um autoteste de módulo traduzido de C++ usando Emscripten, lê a saída do console e retorna o resultado do teste.
Primeiro você precisa instalar o Selenium, para Python 3-Ubuntu isso é feito assim:

pip3 install selenium

Em seguida, baixe o ChromeDriver do site oficial, coloque o chromedriver em /usr/local/bin, por exemplo, depois disso você pode começar a implementar o autoteste.
Abaixo darei o código de autoteste que inicia o navegador Chrome com a página de autoteste aberta no Emscripten, verifica a presença do texto “Teste de janela bem sucedido”:

import time
from selenium import webdriver
from selenium.webdriver.common.keys import Keys
from selenium.webdriver.common.desired_capabilities import DesiredCapabilities

capabilities = DesiredCapabilities.CHROME
capabilities['goog:loggingPrefs'] = { 'browser':'ALL' }
driver = webdriver.Chrome()
driver.get("http://localhost/windowInitializeTest/indexFullscreen.html")

time.sleep(2)

exitCode = 1

for entry in driver.get_log('browser'):
    if entry["source"] == "console-api":
        message = entry["message"]
        if "Window test succeded" in message:
            print("Test succeded")
            exitCode = 0

driver.close()
exit(exitCode)

Salve o teste como main.py e execute python3 main.py