libnds #3 Kafelkowe tło

Przygotowanie

Za podstawę do napisania kafelkowego tła posłużą:

Przykład z libnds:
devkitPro/examples/nds/Graphics/Backgrounds/all_in_one

Pojedyńczy obrazek tła ze spelunky community update:

SpelunkyCommunityUpdateProject/spelunky/Sprites/Blocks/Background/sCaveBG.images/image 0.png

Program do edycji map na NDS/GBA:

http://www.tilemap.co.uk/mappy.php

Odpowiednie kroki

1

Obrazek wskazany wyżej trzeba najpierw przepuścić przez poniższą stronę:

https://online-converting.com/image/convert2bmp/

Wybieramy tryb 8 (indexed).

Po pobraniu wrzucam go podpisanego jako cavebg.bmp do folderu gfx/tilemaps. W nim napisałem następującą regułę grit (wytłumaczenie – odsyłam do docsów grit):

-p!
-gt
-gB8
-mRtpf
-mLs
-mu32
-Mw16
-Mh16

Mój Makefile (gdzie wskazuję gritowi jakie foldery ma odwiedzić) możecie sprawdzić na Githubie spelunky-ds.

2

Teraz kopiujemy odpowiednie pliki z przykładowego projektu do naszego projektu:

  • scrolling.cpp
  • TextBackgrounds.s

Do main.cpp wystarczy skopiować jedynie linie (podmieniłem argument tak aby pasował do naszego obrazka cavebg):

dmaCopy(cavebgTiles, bgGetGfxPtr(bg), sizeof(cavebgTiles));
dmaCopy(Layer256x256Map, bgGetMapPtr(bg), Layer256x256MapLen);
dmaCopy(cavebgPal, BG_PALETTE, cavebgPalLen);

3

Robimy mapę. Ściągamy edytor który podlinkowałem wyżej.

Tworzymy nową mapę przez File->New map. Korzystamy z faktu, że pojedyńczy tile w NDS jest rozmiarów 8×8, nasz obrazek to 32×32 a rozmiar mapy jaki wybraliśmy to 256×256 – będzie więc miała szerokość i wysokość 32, szerokość i wysokość tile-a 8×8 co podajemy w oknie które wyskoczy.

Importujemy obrazek .bmp który stworzyliśmy wcześniej opcją File->Import.

Rysujemy cokolwiek i eksportujemy do pliku txt przez File->Export as text, w oknie które się pojawi niczego nie zmieniamy.

W pliku txt który się wygenerował interesuje nas pierwsza tablica od góry.

Ponieważ nie do końca wiem, czy to jakaś rzecz wynikająca z C++ czy mój błąd, na razie nie kopiuję tej tablicy bezpośrednio do kodu, ale podmieniam wartości w pliku TextBackgrounds.s – inaczej nie działa.

Miejsce które trzeba podmienić, to Layer256x256Map (ponieważ taki rozmiar mapy wybraliśmy). Miejsce to deklaruje wygląd mapy.

Screenshot from 2018-02-25 17-50-58

Wyrzucamy wszystko co jest po Layer256x256Map i jest przed:

@}}BLOCK(Layer256x256)

Teraz ważna rzecz – nie wklejamy tu bezpośrednio tej tablicy. Przepuszczamy ją przez prosty program który napisałem (zmienia tablicę 2d na 1d, zmienia wartości z decymalnych na hexy + dodaje “.hword” na początku każdej linii) wklejamy dopiero output, który wypuścił ten program.

Wrzuciłem jego source do Githuba projektu, do folderu utils. Przed uruchomieniem trzeba wkleić swoją własną mapę do jego kodu.

Wynik

Mamy scrollowalną mapę jak poniżej:

myimage

Co dalej

Zastanawiałem się więc w którą stronę pójść – wyświetlać jako tiled background jedynie te faktycznie statyczne elementy (tło które jest za niszczalnymi elementami), wyszczególnione tutaj:

background

…a zniszczalne elementy wyswietalać jako sprajty. Wtedy logika wyświetlania zniszczonych elementów byłaby prostsza, zero kombinowania, tak samo sprawdzanie kolizji, np. z kolcami czy podmiana sprajta, jeśli np. ten element wybuchł. Plus wszystkie wartości pomocnicze trzymane byłyby w jednej strukturze.

Pytanie tylko, czy wyświetlanie tego w ten sposób jest dobre – NintendoDS ma rzekomo oddzielny układ odpowiedzialny za wyświetlanie backgroundów, nie obciążałbym więc CPU, po prostu kopiowałbym pamięć do odpowiedniego rejestru przez Direct Memory Access, gdybym nie używał sprajtów tylko wyłącznie background. Być może NDS ma też oddzielny układ do wyświetlania sprajtów i nie musiałbym zastanawiać się jak będzie to wyglądać wydajnościowo – problem w tym:

On the Nintendo DS, we can have up to 128 sprites.

https://patater.com/files/projects/manual/manual.html#id2614195

Więc raczej by to nie wyszło, mapa w Spelunky to około 40×40, nie mówiąc o postaciach czy przeszkodach.

Size was one of the benefits of using tilemaps, speed was another. The rendering of tilemaps in done in hardware and if you’ve ever played PC games in hardware and software modes, you’ll know that hardware is good. Another nice point is that scrolling is done in hardware too. Instead of redrawing the whole scene, you just have to enter some coordinates in the right registers.

https://www.coranac.com/tonc/text/regbg.htm

Drugi pomysł, wykorzystujący w 100% tylko backgroundy, to napisanie pomocnicznego programu, który przejdzie przez plik txt z generatora map i stworzy tablicę elementów (powiedzmy, że nazwiemy te elementy SpriteElement {x, y, typ elementu (zwykły klocek, klocek tła, itd), boolan czyZniszczony, szerokość, wysokość, wskaźnik na tablicę intów który będzie wskaźnikiem na hexy ekwiwalentu tego samego tile-a, ale zniszczonego}).

Wtedy za każdą zmianą takiego kawałka tła (np. zniszczeniem pojedyńczego klocka) będzie można robić wpis do rejestru ze zmienioną tablicą i tło nadal będzie się jakoś wyglądać – to które to będą element listy i na jaką wartość ją podmienić będzie wiadomo ze SpriteElement. Kolizje i odpowiednia logika również wyszłaby z tego.

Plus, i tak muszę zrobić coś co będzie w stanie wygenerować mapę od zera (w Spelunky każda mapa jest losowa, generowana proceduralnie) więc jakieś makra pod poszczególne kafelki będę musiał gdzieś w kodzie zadeklarować.

 

Wkrótce napiszę jakąś wstępną implementację.

Efekt powyższego tutoriala można zobaczyć na Githubie tego projektu:

https://github.com/dbeef/spelunky-ds

 

PS: Zauważyłem, że kolejne hexy: 0x0001, 0x0002, 0x0003…0x000F to kolejne elementy (8×8 tile) naszego obrazka .bmp. Składa się to w całość – gdyby ułożyć je warstwami po 4, narysowalibyśmy nasz obrazek. Można w ramach eksperymentu wkleić coś takiego do pliku TextBackgrounds.s:

.hword 0x0000,0x0001,0x0002,0x0003,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x0004,0x0005,0x0006,0x0007,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000


.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x0008,0x0009,0x000A,0x000B,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000
.hword 0x000C,0x000D,0x000E,0x000F,0x0000,0x0000,0x0000,0x0000

…powinno narysować klocek + powtarzający się, lewy górny róg klocka wokół.

 


Przydatne linki:

libnds

https://www.coranac.com/tonc/text/objbg.htm

https://www.coranac.com/tonc/text/regbg.htm

https://gbatemp.net/threads/ds-programming-for-newbies.322106/

https://gbatemp.net/threads/tile-mapping-libnds-or-palib.325728/

C++

https://stackoverflow.com/questions/1238613/what-is-the-difference-between-the-dot-operator-and-in-c

https://stackoverflow.com/questions/54585/when-should-you-use-a-class-vs-a-struct-in-c

https://stackoverflow.com/questions/38942013/declaring-variables-in-header-files-c

https://stackoverflow.com/questions/10198046/c-member-variables

https://stackoverflow.com/questions/185844/initializing-private-static-members

https://stackoverflow.com/questions/20019441/how-is-a-header-file-being-compiled-into-the-executable-file

Konfiguracja Code::Blocks pod NDS:

https://whatroidoes.wordpress.com/2014/01/09/nds-development-tutorial-how-to-use-devkitpro-with-codeblocks-and-debug-with-insight/

 

 

libnds #2 Piszemy intro – timery

 

Wziąłem się za ustawienie środkowiska pod libnds (nie będę w końcu pisał całej gry w vimie). Pobrałem CLiona, żeby mieć ze sobą wszystkie najlepsze udogodnienia z Intellij którego używam na codzień do Javy – problem w tym, że CLion nie ma wersji community, jedynie 30 dniowy trial. Trzeba będzie pojanuszować i ściągać ponownie za miesiąc (jakoś nie mam ochoty na wydawanie 200€ na rok).

Wrzuciłem też gotowy projekt na githuba, teraz można śledzić progress:

https://github.com/dbeef/spelunky-ds

Co chcemy osiągnąć:

introScreen z intra Spelunky

Na start gry, zdanie po zdaniu, z interwałem ~2.5s, odkrywane są kolejne linie intra. Chcemy napisać klasę, która będzie odpowiedzialna za takie przerywniki.

Za szablon wziąłem sobie plik z przykładów devkitPro/examples/nds/Graphics/Printing/customFont.

To jest miejsce w którym zapoznam się z timerami w libnds. Każda z linii pojawia się co określony odstęp czasu, który trzeba sobie odliczyć. Z tego co znalazłem w docsach i wypróbowałem, za odliczanie czasu odpowiada specjalny układ na płytce DSa, a właściwie jeden z czterech układów, w zależności który wybierzemy.

Start i zatrzymanie układu wygląda następująco:

Screenshot from 2018-02-21 12-44-41

Wygląda to tak:

  • w pierwszym argumencie podajemy który timer używać
  • w drugim podajemy jakiego dzielnika używać, czytaj – co jaki czas ma być naliczany ‘tick’ timera
  • trzeci – liczba ticków która musi minąć, zanim bufor timera się przepełni
  • funkcja która ma być wywołana w momencie, kiedy bufor się przepełni

Przykładowo, napisałem taki kod, który ma za zadanie co około sekundę wypisać na konsolę NDS czas  jaki upłynął (wytłumaczenie w komentarzach):

Screenshot from 2018-02-21 13-06-10

Efekt wygląda tak:

myimage

Wracając więc do tego co mamy zrobić, to inicjalizujemy zmienne int trzymające wartości czasu w milisekundach i zdejmujemy z nich upłynięty czas. Jeśli upłynął i nie ustawiliśmy jeszcze flagi ‘narysowano’, to wywołujemy funkcję wypisującą na konsolę i ustawiamy flagę na 1. Robimy tak dla każdej z trzech linii.

Timery dla każdej z linii ustawiłem jako tablicę:

{1000, 3500, 6000}

Z czego można się domyślić, że pierwsza linia wyskoczy po sekundzie, druga po 3.5, trzecia po 6.

Efekt:

myimage

 


 

Linki:

https://devkitpro.org/viewtopic.php?f=6&t=1622

Kindle 4 jako linuksowy terminal

Przyszło mi do głowy, aby zrobić użytek z rozbitego Kindla którego już nie używam. Myślałem na początku o stacji pogodowej (Kindle obsługuje javę, więc może nawet  mógłbym napisać coś własnego po wrzuceniu jailbreak-a), ale wtedy zobaczyłem to:

Okazuje się, że sporo osób włożyło wysiłek w to, aby móc używać Kindle jako ekranu terminala (mógłby mi się przydać, jako dodatkowy ekran na listę rzeczy do zrobienia, do wrzucenia htop-a i monitorowania zasobów albo irca).

Udało mi się, efekt wrzucam tutaj, a poniżej zagregowałem wszystkie materiały, które są potrzebne aby krok po kroku przeprowadzić to samo na innym Kindlu 4 (non-touch), razem z własnymi uwagami i zdjęciami (efekt spodobał mi się na tyle, że zrobiłem to samo także na drugim, sprawnym Kindlu, więc była okazja na spisanie/zrobienie zdjęć ze wszystkiego).

Przykładowy manual wyświetlony na Kindlu:

man

Htop z mojego laptopa, wyświetlany na kindlu:

htop

Midnight commander

mc

Irc

irc

 


Instrukcje

Nie ponoszę odpowiedzialności za zepsute Kindle!!!

Max czas jaki zajmie wszystkiego poniżej to 60 minut.

1

Pierwszym co trzeba zrobić, to zainstalować jailbreak stworzony przez społeczność.

Wersja pod Kindle 4 NT wraz z instrukcjami i odpowiednim plikiem jest tutaj:

https://wiki.mobileread.com/wiki/Kindle4NTHacking#Jailbreak

Ważna rzecz – spiszcie sobie gdzieś lub zróbcie zdjęcie numeru seryjnego waszego Kindla – będzie potrzebny w punkcie 4.

Numer seryjny będzie wyświetlony w menu diagnostycznym które pojawi się, kiedy będziecie przechodzić przez instrukcje od jailbreaka, będzie wygladać tak jak na zdjęciu poniżej:

 

Inna rzecz którą wydaje mi się, że nie można pominąć, to sprawdzić wersję softu – u mnie na obu Kindlach było to 4.1.3, a podlinkowany jailbreak powinien działać od 4.0.0 do 4.1.3. Wersję softu można sprawdzić w ustawieniach, będzie wypisana na dolnym pasku.

Poza tym, wydaje mi się, że nie ma tu zbyt wiele do tłumaczenia.

Paranoicy mogą też podładować baterię do 100% przed całą operacją.

Po skopiowaniu wskazanych w tutorialu plików na wierzch pamięci Kindla i przejściu przez resztę kroków, podczas uruchamiania pojawi się taki ekran:

jailbroken

2

Drugi krok, to instalacja usbnetwork – pozwoli to po podłączeniu Kindla kablem USB udawać komunikację przez ethernet (mniam), zainstaluje serwer ssh na Kindlu plus zdejmie ekran “USB Drive Mode”, kiedy Kindle jest podłączony do komputera (przyda się później).

Odpowiedni plik wskazany jest tutaj:

https://wiki.mobileread.com/wiki/Kindle4NTHacking#SSH

Przy czym na dzisiaj (i pewnie już na zawsze, patrząc na to kiedy stworzony był ten hack), aktualną wersją pod Kindle 4 jest:

https://www.mobileread.com/forums/attachment.php?attachmentid=141341&d=1440341478

Instrukcje z README_FIRST.txt z pobranego pliku powinny być jasne, ale je powtórzę:

  • Kopiujemy plik Update_usbnetwork_0.57.N_k4_uninstall.bin na wierzch pamięci Kindla (tak jak w przypadku jailbreaka)
  • Uruchamiamy instalację poprzez:
    • [Menu] -> Settings -> [Menu] -> Update Your Kindle.

Stosowne zdjęcie wymienionego ekranu:

update

3

Po restarcie poprzedzonym instalacją usbnetwork jesteśmy gotowi, żeby połączyć się z Kindlem przez ssh.

Noooo prawie. To co trzeba zrobić po każdym restarcie, aby uaktywnić usbNetwork, to:

  • Wcisnąć przycisk klawiatury, wpisać ;debugOn (razem ze średnikiem), wcisnąć klawiaturowe “Done”, a następnie search my items” z paska. Po wszystkim nie będzie żadnej widocznej reakcji, Kindle po prostu odświeży ekran.
  • Po tym, zrobić to samo, ale wpisać ~usbNetwork (razem z tyldą)

 

Teraz można podłączyć Kindle przez kabel usb.

Po podłączeniu Kindla, można ustawić sobie adres poprzez ifconfig, ale z tego co zauważyłem, połączenie lubi się zrywać po kilkudziesięciu sekundach, jeśli połączenie nie będzie dodane do Network Managera.

Z readme dowiadujemy się, że Kindle 4 będzie przyjmował połączenia tylko z adresu 192.168.15.201, więc po podłączeniu go edytujemy powstałe połączenie (Ubuntu -> “Network connections”) i ustawiamy taki przez interfejs gnome do Network Managera.

Screenshot from 2018-02-18 21-04-57

Dla niezaznajomionych z notacją CIDR aka “dlaczego tam jest 24”:
https://pl.wikipedia.org/wiki/Classless_Inter-Domain_Routing

W tym momencie jesteśmy gotowi do połączenia ssh!

4

Noooo i znów, prawie.

Statyczny adres, pod jakim Kindle będzie w sieci, to 192.168.15.244.

Tutaj przyda się numer seryjny który spisaliśmy wcześniej. Po nim dowiemy się, jakie są możliwe hasła roota do Kindla. Wpisujemy go pod poniższym adresem:

https://www.sven.de/kindle/

I sprawdzamy, które z wygenerowanych haseł będzie pasować.

pass

Zostało już tylko zainstalować emulator terminala i jesteśmy w domu!!!

5

To od czego trzeba zacząć, aby terminal w ogóle miał szansę się uruchomić, to wrzucić keystore deweloperów Kindle.

Opisane jest to tutaj:

https://wiki.mobileread.com/wiki/Kindlet_Developer_HowTo#How_To_install_the_merged_developer.keystore_on_the_Kindle

Polecam jednak rozegrać to trochę inaczej – w końcu mamy teraz dostęp przez ssh.

Rozpakowujemy na komputerze pobrany keystore (na tę chwilę jest to 2012-11-06) i odpalamy Midnight Commander.

W otwartej wcześniej sesji ssh, wpisujemy mntroot rw, a w oknie Midnight Commandera. Wybieramy w lewym górnym rogu [Left] -> [Shell link] -> [root@192.168.15.244].

Po zalogowaniu się, przechodzimy do /var/local/java/keystore/.

Jest możliwość, że zastaniemy tam już istniejący plik o takiej samej nazwie, wtedy zatrzymujemy go w razie czego pod inną nazwą, np. poprzez [F6] i wpisanie *_old i kopiujemy nasz developer.keystore.

keystores

Po całości trzeba zrestartować Kindle (keystore ładowany jest tylko raz, na start), co za tym idzie od nowa wpisywać ;debugOn i ~usbNetwork – jeśli chcecie sobie tego zaoszczędzić, to przejdźcie od razu do następnego punktu, bo po nim również przyda się restart.

6

Instalujemy i włączamy emulator terminala.

Autor bloga z tego linku:

http://pepijndevos.nl/2012/10/08/kindle-4-as-a-paper-terminal.html

zrobił super robotę, zmienił i skompilował javowy emulator z Kindle w wersji dotykowej/w wersji z klawiaturą na wersję która uruchomi się na Kindle 4 który nie ma żadnego z wymienionych.

Powstaje pytanie – jak w takim razie wpisać jakąkolwiek komendę na takim Kindlu? To za chwilę.

Ściągamy jego wersję terminala:

https://github.com/pepijndevos/KindleTerm/downloads

I kopiujemy ją (kindleterm.azw2) do katalogu ‘documents‘ który jest na wierzchu pamięci Kindla (jeśli chcemy to zrobić przez mc, to miejsce to jest zamontowane w /mnt/us).

Po tym modyfikujemy plik /opt/amazon/ebook/security/external.policy w taki sposób, aby po “grant signedBy “Kindlet” {”  zawierał linie:

permission java.net.SocketPermission "localhost:1024-", "accept, connect, listen";
permission java.net.SocketPermission "192.168.15.201", "connect, accept";
permission java.net.SocketPermission "localhost", "connect, accept";

Jeśli pojawia się błąd podczas zapisu pliku, w terminalu trzeba wcześniej wpisać mntroot rw.

Po całości wpisujemy mntroot ro i reboot. Teraz Kindle powinien się zrestartować.

6

Po restarcie standardowo – odłączamy Kindla od kabla, ;debugOn, ~usbNetwork i znów podłączamy.

Po ostatnim punkcie, w bibliotece Kindla powinna pojawić się pozycja KindleTermPV:

kidnleterm34

Otwieramy KindleTermPV.

kindleterm

Program ma jakiś bug i po włączeniu nie zawsze wszystko się wyświetla, wtedy są 3 możliwości:

  • Kilka razy kliknąć enter na joysticku
  • Przycisk ‘return’ i włączyć od nowa
  • Wcisnąć jednocześnie ‘return’ + ‘keyboard’.

Teraz wracamy do pytania – jak tu coś wpisać?

Tymczasowo (dopóki nie podłączymy się na Kindlu do sesji tmuxa) potrzebny będzie program robiący za wirtualną klawiaturę.

Opis i autor jest tutaj:

https://www.mobileread.com/forums/showpost.php?p=2251897&postcount=60

Wykonujemy instrukcje, czyli na Kindlu:

iptables -I INPUT -p tcp --dport 3333 -j ACCEPT

a na komputerze tworzymy plik o nazwie remote_keyboard.properties z taką zawartością:

host 192.168.15.244
port 3333

Wtedy umieszczamy w tym samym miejscu co powyższy plik wrzucony wcześniej na Kindla KindleTERM i odpalamy:

java -cp kindletermpv.azw2 kindle.RemoteKeyboard

cat

Powinno pojawić się okno swingowej aplikacji – klikamy w jego środek i piszemy cokolwiek – dokładnie to samo powinno pokazać się na ekranie Kindla!

dbeef

Jak pozbyć się tej aplikacji i pisać bezpośrednio w terminalu z komputera? Z pomocą przychodzi tmux i serwer telnet. Wszystko idzie po kablu usb, więc wątpię żeby użycie telnetu było jakimś zabezpieczeniowym faux-pas, chyba że ktoś zdecyduje się łączyć z Kindlem po wifi (nie próbowałem).

Jeśli jeszcze nie mamy, to instalujemy serwer telnet i aplikację tmux.

Gdy już mamy to:

  • Na komputerze wpisujemy ‘tmux’
  • Na Kindlu wpisujemy ‘telnet 192.168.15.201’ i logujemy się na swoje konto z komputera.
  • Na Kindlu wpisujemy  export TERM=ansi (bez tego nie zadziała tmux ani praktycznie nic innego)
  • Na Kindlu wpisujemy ‘tmux ls’, zapamiętujemy numer sesji która ma najnowszą datę utworzenia
  • Na Kindlu wpisujemy ‘tmux attach -t [numer sesji, np. 2]

Gotowe !!!

Teraz cokolwiek będzie wpisanego na komputerze, pojawi się na oknie na Kindlu (można wyłączyć już javową apkę).

28217548_1625339264185793_1093522813_o

Koniec.

Duże podziękowania dla wszystkich osób które udostępniły potrzebne materiały na blogach/forach.

Wpis na blogu w którym opisane jest jak zautomatyzować proces łączenia tak, żeby używać Kindla w charakterze ekranu dla Raspberry:

https://projectdp.wordpress.com/2012/09/24/pi-k3w-kindle-3-display-for-raspberry-pi/

 


Linki

 

Instalacja linuksowych aplikacji na kindlu ( i mikro package manager):

http://www.timelesssky.com/blog/linux-apps-for-kindle

Stacja pogodowa na kindlu 4 NT:

https://github.com/ufuchs/weather-on-kindle4nt

Co zrobić jeśli przerywa połączenie:

https://www.mobileread.com/forums/showthread.php?t=158015

 

 

John the ripper, myślałem na początku o wydobyciu hasła do roota z zakodowanego /etc/shadow (defaultowo można zalogować się na użytkownika o standardowych uprawnieniach bez generatora haseł, u:framework p:mario, wtedy można wydobyć ten plik).

Zastanawiało mnie trochę zrobienie tego na kilku urządzeniach jednocześnie (jeśli byłoby konieczne iteracyjne odgadywanie haseł), bo okazuje się że JTR używa tylko jednego rdzenia – odgadnięcie hasła zajęłoby tygodnie działania.

Obeszło się bez użycia JTR, ale to jest to co znalazłem przy okazji:

http://www.openwall.com/john/doc/EXAMPLES.shtml

https://en.wikipedia.org/wiki/Data_Encryption_Standard

https://blog.thireus.com/crack-passwords-using-john-the-ripper-with-multiple-cpu-cores-openmp/

http://www.admin-magazine.com/Articles/John-the-Ripper

http://www.cs.tufts.edu/comp/116/archive/fall2013/tlubeck.pdf

https://www.oiepoie.nl/2007/02/11/high-speed-password-cracking-with-john-the-ripper/

https://moveaxeip.wordpress.com/2011/11/10/distributed-password-cracking-with-john-the-ripper/

 

libnds #1 Przedstawienie libnds i Spelunky

W tej serii na warsztat chcę wziąć istniejącą grę Spelunky i przepisać ją na konsolę Nintendo DS.
W pierwszym poście chcę jedynie pokazać możliwości a nie wprowadzić od podstaw do libnds – to być może przedstawię w innych postach (pisanie na dsa wydaje mi się dobrym wprowadzeniem do programowania na systemach embedded), tymczasem poniższe jest ciekawostką.

Przedstawienie Spelunky

Spelunky to darmowa gra napisana przez Dereka Yu w 2009 (która dorobiła się kontynuacji w 2012) z gatunku cave-exploration.

Spelunky is a cave exploration / treasure-hunting game inspired by classic platform games and roguelikes, where the goal is to grab as much treasure from the cave as possible. Every time you play the cave’s layout will be different. Use your wits, your reflexes, and the items available to you to survive and go ever deeper! Perhaps at the end you may find what you’re looking for…

Można ją pobrać ze strony autora, tutaj:

http://www.derekyu.com/games/spelunky_1_1.zip

Wydanie Spelunky przypadło na moje lekcje informatyki w gimnazjum (R.I.P), nie miało konkurencji przez to że waży tylko 9.5 MB, nie wymaga instalacji i działa bez problemu przez Wine.

Co istotne, Derek Yu udostępnił kod i inne zasoby gry na poniższej licencji;

http://www.spelunkyworld.com/files/COPYING.txt

…więc jest to świetny cel do przeniesienia na inną platformę (pomijając fakt że Spelunky zrobione są w Game Makerze i wydobycie czegoś z udostępnionych plików .gmk wymaga posiadania wymienionego).

Gameplay z komentarzem:

 

Wydobycie grafik

Znalezienie assetów oryginalnych Spelunków zacząłem nie od Game Makera ale od Githuba (z przeczucia że ktoś już próbował ruszyć temat).

To co znalazłem, to:

Właśnie to ostatnie było tym czego szukałem, skatagolowane pliki gry z odpowiednimi podpisami i kodem. Miałem już wszystko co potrzebne.

Przedstawienie libnds

Libnds wraz z przykładami dostarczany jest wraz z projektem devkitPro który zbiera wszystkie narzędzia potrzebne do pisania amatorskich programów na ds-a.

Do zautomatyzowanej instalacji devkitPro na linuksie udostępniony jest skrypt który wystarczy uruchomić interpreterem perla:

https://sourceforge.net/projects/devkitpro/files/Automated%20Installer/devkitARMupdate.pl/download

Po całej operacji brakuje tylko jednej rzeczy – emulatora NintendoDS – tutaj zdaje się że najlepszą opcją jest desmume.

Po przejściu do ~/devkitPro/examples/nds/Graphics i pierwszym uruchomieniu narzędzia make poproszeni zostaniemy o dodanie zmiennych DEVKITPRO i DEVKITARM do /etc/environment.

Po drugim uruchomieniu zbudowane zostaną pliki .nds, które będzie można włączyć emulatorem. Np. ~/devkitPro/examples/nds/Graphics/3D/3D_Both_Screens:

Screenshot from 2018-02-03 17-42-14.png

Zamierzam zrobić jakiś mały tutorial pisania na ds-a w następnych postach, więc daruję sobie przedstawianie szczegółów teraz. Gdyby ktoś szukał materiałów do nauki, to w kolejności od moim zdaniem najlepszych:

  • Patater + wspomniane przykłady od devkitPro

https://github.com/Patater/manual

https://patater.com/manual/

  • (niedokończony) tutorial z Githuba :

https://github.com/jdriselvato/NDS-Development/tree/master/examples/Graphics

  • (krótki) tutorial z czyjegoś bloga:

https://www.liranuna.com/nds-2d-tuts

  • W każdym z powyższych tutoriali przydaje się wyszukiwanie detali w docsach od libnds:

http://libnds.devkitpro.org/dma_8h.html#ac77a16a7cb9f2fa2b4361c22fe84245d

  • Czyjaś gotowa gra tekstowa:

https://github.com/richelbilderbeek/CityOfThieves

 

Użycie oryginalnej czcionki Spelunky do programu na ds-a

Najprostsze wprowadzenie jakie może być, bo polegające na wypisaniu tekstu w konsoli-konsoli. Jedyna różnica, to użycie czcionki innej niż systemowa.

 

Na bazie przykładu z ~/devkitPro/examples/nds/Graphics/printing/custom_font widać, że potrzebny będzie tilesheet z złączonymi wszystkimi znakami jakie potrzebujemy, aby móc pisać własną czcionką na ekranie ds-a.

W pobranym SpelunkyCommunityUpdateProject /spelunky/Sprites/sFont.images dostępne jest 59 znaków (od spacji do ‘Z’) w oddzielnych plikach ponumerowanych od 0 do 58, co odpowiada kodom znaków z tabeli ASCII przesuniętym o 32 (istotne później):

asciifull

Do złączenia tych znaków w jeden plik wykorzystałem narzędzie online Stitches:

http://draeton.github.io/stitches/

Aby Stitches nie zmieniło kolejności i wygenerowało jedną kolumnę ze znakami dokładnie w tej kolejności jak w tabeli ASCII, musiałem zmienić nazwy plików ze znakami tak jak poniżej (inaczej mocno się przetasowywało), czyli co 10 plików dodając kolejną literę alfabetu:

Screenshot from 2018-02-03 18-10-29

Po całej operacji Stitches wygenerowało taki plik:

spritesheet

Teraz ważna rzecz:

używane grafiki, muszą przejść przez (dołączony w devkitPro) program grit, wtedy w kodzie dołączone są jako plik nagłówkowy (z obrazek.bmp powstaje obrazek.h dołączony jako #include <obrazek.h>). Wytłumaczenie z tutoriala patater:

Working with the Makefile

The default template makefile will turn your graphic files into object files for linking into your program. Never include data as a header file.

The graphics must be in a lossless image format, such as gif, tif, bmp, or png in order to work with the provided template makefile. I prefer the png graphic format. Image conversion is usually done by a program called grit. The provided template makefile will ask grit to convert images in the gfx folder of your project root to a format ready for the Nintendo DS.

The provided template makefile, adapted from the default libnds template makefile, is a good base for most all projects. It will look in a folder called gfx (in the same directory as the makefile) for your graphics. If any are found, it uses a special bin2o rule to tell grit to turn your images into .o files, according to grit rule files (with the .grit files extension), which can be linked into your program. grit will create a header file (.h) for your data. The name format for them works like so: if a file is called orangeShuttle.png the header file will be called orangeShuttle.h. Inside this header file will be a reference to the data in the .o, named orangeShuttleTiles and orangeShuttlePal or orangeShuttleBitmap, depending on how the grit file specifies which format to convert your image into. It will also include the length in bytes of the data references as orangeShuttleTilesLen and orangeShuttlePalLen or orangeShuttleBitmapLen.

For our project, we’ll be putting the our graphic files and grit rule files into the gfx directory and having the makefile use grit on them.

Jeśli teraz nie rozumiecie, to po rzuceniu okiem na kod wszystko się wyjaśni.

Otrzymany obrazek .png koniecznie konwertujemy na .bmp z 4 lub 8 bitową głębią kolorów, dowolnym narzędziem, ja wykorzystałem to:

https://online-converting.com/image/convert2bmp/ 

…i wybrałem opcję ‘8 (indexed)’.

Trzeba dodać ważną rzecz – jak wrzucić font w formacie bmp, aby zawierał przeźroczyste obszary tzn. znak/cyfra na przeźroczystym tle (format bmp nie wspiera kanału alfa – przeźroczystości)?

Wybieramy kolor który nie pojawia się w czionce (piksele o tym kolorze będą interpretowane jako przeźroczystość), sprawdzamy jego wartość w hexach i wrzucamy do pliku grit z przykładu. Przykład z docsów grit:

NDS 16bpp bitmap, with cyan as transparent color
  -gb -gB16 -gT 00FFFF

Dopisuję odpowiednią flagę wraz z wartością (209c00) i edytuję spritesheet w gimpie, zmieniając tło znaków/liter/cyfr na zielony #209C00:

Screenshot from 2018-02-03 18-36-10

Zerknijmy teraz na kod który wypisze nasz tekst na ekran ds-a:

Screenshot from 2018-02-03 18-38-34

Tutaj jak wspomniałem wcześniej, przydaje się znajomość od którego znaku ASCII zaczynamy nasz spritesheet (linia z font.asciiOffset = 32).

W powyższym kodzie pojawia się kilka makr i funkcji biblioteki nds, nie ma co przedstawiać ich tutaj wybiórczo bo potrzebny jest do tego trochę pełniejszy obraz który można znaleźć w wymienionych wcześniej tutorialach.

Całość kompilujemy i włączamy emulatorem:

Screenshot from 2018-02-03 18-43-46

Koniec części 1.

 

Inne

Konfiguracja ndslib pozwalająca jednocześnie wypisywać konsolę + rysować sprite-y:

https://gamedev.stackexchange.com/questions/61065/using-ndslib-how-to-configure-video-modes-to-both-print-text-and-draw-bitmaps-o

 

Coś co mnie zastanawiało przeglądając przykłady ndslib:

https://stackoverflow.com/questions/30896489/why-is-u8-u16-u32-u64-used-instead-of-unsigned-int-in-kernel-programming

 

Operatory binarne w cpp takie jak ‘|’ czy ‘&’ są tu co chwile używane przy zmienianiu wartości rejestrów, warto się zapoznać:

https://www.tutorialspoint.com/cplusplus/cpp_operators.htm

 

Parę słownikowych terminów które się pojawi:

https://stackoverflow.com/questions/4917205/interrupt-masking-why

https://pl.wikipedia.org/wiki/Direct_Memory_Access

https://pl.wikipedia.org/wiki/Przerwanie

 

c++:

https://stackoverflow.com/questions/2575048/arrow-operator-usage-in-c

https://stackoverflow.com/questions/33333144/using-void-as-c-equivalent-of-java-object

https://stackoverflow.com/questions/4269034/what-is-the-meaning-of-prepended-double-colon

https://stackoverflow.com/questions/4269034/what-is-the-meaning-of-prepended-double-colon

Jak działają bitmapy:

http://paulbourke.net/dataformats/bitmaps/

https://pl.wikipedia.org/wiki/Głębia_koloru

 

 

 

Zabawy z Onion Omega 2

Onion to de facto router, za 45 zł, z gpio i przerobionym przez producenta openwrt. Rozmiary + cena oniona przewraca mój świat do góry nogami.

Żeby pokazać jakie to jest maleństwo zestawiłem od lewej:

27394066_1602885673097819_81576568_oOnion, Arduino micro, Arduino uno, Orange PI one, Raspberry Pi 3.

~

Schemat zabawy:

  1. Stawiamy na onionie serwer http (uhttpd) hostujący angularową stronę, którą można podejrzeć na http://www.c-y-r-k-i-e-l.pl (ta jest akurat hostowana na prawdziwych serwerach)
  2. Instalujemy htop
  3. Testujemy obciążenie przez jmeter

Przygotowania

input_kable

Plus i minus jest na dwóch pierwszych pinach od strony z wcięciem.

Absurdem jest, że rozszerzenie do zasilania oniona po usb kosztuje więcej niż sam onion. Całe szczęście mamy zasilacz renomowanej chińskiej marki (sugestywna cisza)…

zasilaczOnion przyjmuje 3.3 V, lepiej nie ustawiajcie 3.5 V jeśli wierzycie temu co wskazuje wasz zasilacz.

stylowy_radiatorRadiator, model π-FF-KO, wariant 500ML

Celowo pomijam etap konfiguracji, przechodzenie go przez przewodnik hostowany przez oniona w jego sieci to droga przez mękę, polecam od razu połączyć się przez ssh na root@192.168.3.1 (hasło onioneer), skonfigurować dostęp oniona do internetu przez inną sieć wifi poleceniem wifisetup, wykonać polecenie oupgrade, poczekać parę minut na ściągnięcie i flashowanie nowym firmwarem i zacząć się bawić.

 Stawiamy stronę

Defaultowo praktycznie cała pamięć jest zaalokowana na pliki tymczasowe.

Screenshot from 2018-01-26 23-31-30https://en.wikipedia.org/wiki/Df_(Unix)

Nie mam wspomnianego rozszerzenia usb żeby wypalić własny obraz na onionie, więc improwizuję i wrzucam stronę do /tmp/www (taaak, zniknie po rebootcie) i edytuję  /etc/config/uhttpd  (uhttpd jest zainstalowany defaultowo, do hostowania wizarda).

Edytuję tylko jedną linię:

Screenshot from 2018-01-26 23-42-15

Po tym zostaje faktycznie wrzucić stronę w to miejsce:
Screenshot from 2018-01-26 21-56-54

…i zrestartować serwer:

Screenshot from 2018-01-26 23-48-42

Po paru chwilach można spróbować wejść na stronę:
Screenshot from 2018-01-26 20-14-27

HTTP z zapytaniem o zadania nadal trafia do domeny c-y-r-k-ie-l.pl, ale chcę w przyszłości postawić na onionie jakiś mikro serwer z bazą. Tak czy inaczej, można odwiedzić cyrkiel z oniona.

Instalujemy htop

Z niezrozumiałych dla mnie powodów, defaultowe repozytoria jakie są dodane (onionowe, od producenta) nie mają htopa, ale w manualu wskazują jak dodać repo od oryginalnego open-wrt.

Wystarczy więc dodać na koniec pliku /etc/opkg.conf linię:

http://downloads.lede-project.org/snapshots/packages/mipsel_24kc/packages

Cały plik będzie wtedy wyglądał w ten sposób:
Screenshot from 2018-01-26 23-58-30

Dalej zostaje wykonać opkg update, potem opkg install htop i włączyć htopa:

Screenshot from 2018-01-26 20-29-49

Htop przyda nam się do następnego punktu.

Testujemy obciążenie przez jmeter

Jmeter można pobrać bezpośrednio ze strony Apache (i ten sposób polecam, wcześniej pobrałem przez apt, brakowało template-ów które przydały mi się potem).

Otworzyłem szablon do testowania webserwisów i zmieniłem opcje tak, żeby jmeter pobierał wyłącznie stronę główną + wszystkie powiązane pliki.

Podążałem tym tutorialem:

http://jmeter.apache.org/usermanual/build-ws-test-plan.html

Jeśli ktoś chce gotowy scenariusz testowy (chyba za dużo powiedziane ) który z tego wyszedł to wklejam tutaj:

https://pastebin.com/57U1Tvfv

Screenshot from 2018-01-26 21-41-15Test zaczynam od 20 wątków, ramp-up period to czas w jakim wszystkie mają wystartować (5s/20, jeden wątek musi być tworzony co 250 ms żeby wypełnić podany ramp-up). Onion w prawym górnym rogu, jeszcze niczego się nie spodziewa. START.

Screenshot from 2018-01-26 21-59-43Onion w maximum wykorzystania zasobów w trakcie testu, 67 % CPU, średnio 45-55%, max natężenie prądu 0.33 A (w bezczynności oscyluje wokół ~0.17A), cały test trwał mniej niż minutę.

Poradził sobie z 20 wątkami, czemu nie ustawić więc 40?

Screenshot from 2018-01-26 22-01-48

Tu po raz pierwszy pojawia się na chwilę myśl – obciążenie CPU pozostało takie samo, być może nie uda mi się zagotować Oniona takimi testami, bo standard 802.11 jest bottleneckiem?

Rzucam okiem w docsy: onion wspiera b/g/n, Thinkpad T430 a/b/g/n, jakie szybkości oferuje n?

Screenshot from 2018-01-27 09-49-38

Wystarczające żeby przesyłać 75 MB na sekundę max, a minimum 12.5 MB, ergo to nie standard jest problemem tylko karta sieciowa na onionie – przetwarza pakiety na tyle wolno, że kernel zwyczajnie nie dostanie aż tyle pakietów do obsłużenia żeby zapełnić go na 100%!

Do ostatecznego dowodu ustawiam z 40 na 1000 wątków z ramp-up na 1s. Loop-count na 200, tak, aby test trwał minimum kilkanaście minut.

Screenshot from 2018-01-26 22-11-01

Start. Wynik – obciążenie zarówno w pierwszej, w drugiej, dziesiątej i następnych minutach nie przekracza 65 %.

Screenshot from 2018-01-26 22-12-07W prawym górnym rogu znajduje się licznik aktywnych wątków wykonujących test.

Wniosek:
1) Nie upieczesz oniona przez ddos

2) Jak bardzo się postarasz i upieczesz to masz nowego za 45 zł

Edit:

Nie potwierdziłem nigdzie, że faktycznie podłączyłem się do 802.11 w wersji ‘n’, post można uzupełnić tym linkiem:

https://askubuntu.com/questions/173317/how-to-determine-which-wifi-technology-is-currently-used-in-connection

Przydatne linki:

Paczki jakie być może uruchomią się na Omedze, a nie ma ich w defaultowym repo:

https://downloads.lede-project.org/releases/packages-17.01/mipsel_24kc/packages/

Wylistowane komendy busyboxa:

https://busybox.net/downloads/BusyBox.html

Cross-compiling na oniona (stawianie dockera i kompilacja na nim, dopiero potem przerzucenie go na płytkę, upieeeerdliwe)

https://onion.io/2bt-cross-compiling-c-programs-part-1/

Doc od uhttpd:

https://wiki.openwrt.org/doc/uci/uhttpd

Doc opkg:

https://wiki.openwrt.org/doc/techref/opkg

JVM na Onionie, pewnie wypróbuję kiedyś:

http://community.onion.io/topic/36/java-on-omega-with-wrappers/13

TMUL – Not so fast multiplication

Implementując szkolne mnożenie pisemne nie da się rozwiązać tego zadania w czasie oczekiwanym przez spoj, nawet stosując obliczone wcześniej tablice modulo i mnożenia (próbowałem!).

 

Tutaj nie ma sensu wymyślanie własnego alogorytmu, conajwyżej można napisać własną implementację jednego z najszybszych znanych algorytmów:

 

1) Schönhage-Strassen SSA
2) Tom-Cook
3) Karatsuba – Karatsuba c implementation
4) FFT  –   Mutliplication using fft

 

Warto pamiętać że każdy z tych algorytmów ma swój przedział w którym jest najlepszy, ale dla tego zadania wszystkie powyższe będą ok.

 

Zadanie można submitować również w Javie, a ta w klasie BigInteger udostępnia metodę multiply() która dopasowuje rozmiar podanych liczb do najszybszych znanych algorytmów, ale to trochę mało dydaktyczne.

 

Źródła:
Przydał się parę razy do testów:
Rozpisanie istniejących algorytmów:
1)

PA05_POT Czy umiesz potęgować

Zadanie trzeba było rozwiązać zauważając powtarzalność ostatniej cyfry potęgowanej liczby, zwykłe potęgowanie byłoby zbyt złożone obliczeniowo dla podanego zestawu.

Jak zauważyć powtarzalność? Kartka papieru, rozpisać ostatnie cyfry dla 0^1, 0^2, …., 1^1, 1^2, 1^3, …, 9^5 itd.

Potem zapisać odpowiednią tabelę w kodzie, tak aby program sięgał jedynie po odpowiednią wartość z tabeli, zamiast obliczać.

To jak długo wykonuje się progam można sprawdzić pod linuxem za pomocą polecenia ‘time’, np. ‘time wget google.com’, jeśli ktoś chce porównać zwykłą implementację z tą z opisanym chwytem.

Można tu jeszcze użyć stdlib lub wyłączyć synchronizację io w iostream, ale to drobiazgi.

Kod:

#include <iostream>

using namespace std;

int main() {

    unsigned short results[10][1][4] = {{{0}},{{1}},{{6,2,4,8}},
{{1,3,9,7}},{{6,4}},{{5}},{{6}},{{1,7,9,3}},{{6,8,4,2}},{{1,9}},};

    unsigned short modulo[] = {1, 1, 4, 4, 2};

    long n;
    cin >> n;

    long cases[n][2];

    for (long a = 0; a < n; a++)
        cin >> cases[a][0] >> cases[a][1];

    for (long a = 0; a < n; a++) {

        unsigned short moduloDivisorIndex = (cases[a][0] % 5);
        unsigned short moduloDivisor = modulo[moduloDivisorIndex];
        unsigned short lastDigit = cases[a][0] % 10;
        long moduloIndex = cases[a][1] % moduloDivisor;

        cout << results[lastDigit][0][moduloIndex] << '\n';
    }

    cout << endl;

    return 0;
}

Wersja z komentarzem:

#include <iostream>

using namespace std;

int main() {

    //1 indeks jaka jest ostatnia cyfra podstawy
    //3 jaki jest wynik modulo przez komórkę z modulo[]
    unsigned short results[10][1][4] = {
            {       //0
                    {0}
            },{
                    //1
                    {1}
            },{
                    //2
                    {6, 2, 4, 8}
            },{
                    //3
                    {1, 3, 9, 7}
            },{
                    //4
                    {6, 4}
            },{
                    //5
                    {5}
            },{
                    //6
                    {6}
            },{
                    //7
                    {1, 7, 9 ,3}
            },{
                    //8
                    {6, 8, 4, 2}
            },{
                    //9
                    {1, 9}
            },
    };

    unsigned short modulo[] = {1, 1, 4, 4, 2};

    //Pattern na modulo: 1 4 4 2 1
    //Modulo przez 5
    //Dla 1 - 1
    //Dla 2 - 4
    //Dla 3 - 4
    //Dla 4 - 2
    //Dla 0 - 1

    //Liczba: 1
    //Potęgi 1 2 3 4 5 6 7 8 9
    //Wyniki:1 1 1 1 1 1 1 1 1
    //Powtarzanie: [1]

    //Liczba: 2
    //Potęgi 1 2 3 4  5  6  7   8   9
    //Wyniki:2 4 8 16 32 64 128 256 512
    //Powtarzanie: [2 4 8 6]
    //Modulo przez 4:
    //1 - 2
    //2 - 4
    //3 - 8
    //0 - 6

    //Liczba: 3
    //Potęgi 1 2 3  4   5
    //Wyniki:3 9 27 81  243
    //Powtarzanie: [3 9 7 1]
    //Modulo przez 4:
    //1 - 3
    //2 - 9
    //3 - 7
    //0 - 1

    //Liczba: 4
    //Potęgi 1 2  3  4    5
    //Wyniki:4 16 64 256  1024
    //Powtarzanie: [4 6]
    //Modulo przez 2:
    //1 - 4
    //0 - 6

    //Liczba: 5
    //Potęgi 1 2  3   4
    //Wyniki:5 25 125 625
    //Powtarzanie: [5]
    //Modulo przez 1:
    //0 - 5

    //Liczba: 6
    //Potęgi 1 2  3   4
    //Wyniki:6 36 216 1296
    //Powtarzanie: [6]
    //Modulo przez 1:
    //0 - 6

    //Liczba: 7
    //Potęgi 1 2  3   4    5
    //Wyniki:7 49 343 2401 16807
    //Powtarzanie: [7 9 3 1]
    //Modulo przez 4:
    //1 - 7
    //2 - 9
    //3 - 3
    //0 - 1

    //Liczba: 8
    //Potęgi 1 2  3   4    5
    //Wyniki:8 64 512 4096 32768
    //Powtarzanie: [8 4 2 6]
    //Modulo przez 4:
    //1 - 8
    //2 - 4
    //3 - 2
    //0 - 6

    //Liczba: 9
    //Potęgi 1 2  3   4    5
    //Wyniki:9 81 729 6561 59049
    //Powtarzanie: [9 1]
    //Modulo przez 2:
    //1 - 9
    //0 - 1

    //Liczba: 10
    //Potęgi 1
    //Wyniki:10
    //Powtarzanie: [0]
    //Modulo przez 1:
    //0 - 0

    long n;
    cin >> n;

    long cases[n][2];

    for(long a =0;a<n;a++)
        cin >> cases[a][0] >> cases[a][1];

    for(long a =0;a<n;a++){

        unsigned short moduloDivisorIndex = (cases[a][0] % 5);
//        cout << "Modulo divisor index: " << moduloDivisorIndex << endl;

        unsigned short moduloDivisor = modulo[moduloDivisorIndex];
//        cout << "Modulo divisor: " << moduloDivisor << endl;

        unsigned short lastDigit = cases[a][0] % 10;
//        cout << "Last digit: " << lastDigit << endl;

        long moduloIndex = cases[a][1] % moduloDivisor;
//        cout << "Modulo index: " << moduloIndex << endl;

        cout << results[lastDigit][0][moduloIndex] << '\n';
    }

    cout << endl;

    return 0;
}

Sound processing X – Tymczasowe problemy

Zapowiedzianego w ostatnim poście pierwszego próbnego gameplayu nie będzie:

Pomimu kilku prób, mój ThinkPad nie potrafił wydusić z siebie wystarczająco głośnego dźwięku, aby drugi komputer mógł go z powodzeniem odczytać, kończyło się tak, że transmisja była dobra, pomijając w kilku miejsach źle przesłaną cyfrę, co jeśli chodzi o znaki ASCII kończyło się wstawieniem np. znaku pi zamiast dwukropka i w efekcie złym sparsowaniem jsona (modem jest na tyle dobry, że praktycznie zawsze nadawca podsłuchując to co wysyła potrafi to z powrotem sparsować, więc kwestią zostaje głośność).

Prawdopodobnie mógłbym to rozwiązać mikrofonami kierunkowymi, chociaż pozostałby niesmak, że to już nie jest tym, czym było w zamierzeniach (transmisja z urządzenia na urządzenie, bez internetu i specjalnych przyrządów).

Tak czy inaczej, projekt będzie kontynuowany, mam zamiar zakupić pierwszy lepszy kierunkowy mikrofon x2 i nagrać jakiś film, a na ten moment szukam innego wyjścia, w końcu ktoś już napisał podobne aplikacje:

Możliwe, że to kwestia zejścia poziom niżej i napisania własnego wykrywania częstotliwości na podstawie DFT, co nie byłoby takie złe.

W weekend powinien pojawić się nowy post, bo nie sądzę, żebym trafił na ścianę nie do przejścia.


dsp2017-1

Różne V – Sphinx i rozpoznawanie mowy

Jak już wspominałem przy okazji posta z serii Pokaż kod, pisząc Speechlist, na początku byłem nastawiony na rozwiązywanie testów głosem. Częściowo mi się to udało, chociaż przeniesienie tego na telefon nie było łatwe, żeby nie powiedzieć – sprawiało kłopoty, dlatego finalnie je porzuciłem na rzecz zwykłego wstawiania tekstu dotykiem. Zostałem z częściowo już napisanym frontendem pod rozpoznawanie głosu, możecie go zobaczyć w działaniu tutaj:

Kod Speechlist udostępniłem za darmo pod adresem: https://bitbucket.org/dbeef/speechlist

Nie rozpisałem się wtedy co do samego Sphinxa, a to jest temat na większy post.

Czym jest CMUSphinx

CMUSphinx jest opensourcowym narzędziem do rozpoznawania mowy, wspierające C, C++, C#, Python, Ruby, Java, Javascript i rozpoznające m.in. angielski, francuski i niemiecki (chociaż społeczność zbudowała modele rozpoznające także chociażby rosyjski, lista modeli do pobrania jest tutaj).

Wielkim plusem w stosunku chociażby do androidowych usług rozpoznawnia głosu (komunikujących się z serwerami Google) z których można korzystać pisząc aplikacje jest to, że Sphinx działa całkowicie offline.

Do jego działania potrzebne są 3 pliki: acoustic model, dictionary i language model.

Acoustic model zależy od języka i sami go raczej nie stworzymy, pobieramy gotowy z listy którą zamieściłem wyżej. Przykładowo, dla języka angielskiego pobieramy model en-us.

Language model i dictionary generujemy sami za pomocą narzędzi do których odniosę się później, ale można je także pobrać.

Teraz najważniejsze: aby uzyskać niemal 100% skuteczność rozpoznawania, jak na filmiku wyżej, nie używałem gotowego słownika i modelu językowego z ich strony (zawierającego wszystkie słowa). CMUSphinx udostępnia narzędzie, pozwalające zbudować słownik tylko konkretnych słów:

http://www.speech.cs.cmu.edu/tools/lextool.html

Dzięki temu, że zamieściłem tam tylko te słowa, które muszą być rozpoznane w Speechlistowym teście, poprawność była tak dobra, że trudno uwierzyć.

Przy tym wszystkim warto też dodać, jak niewiele zasobów wymaga Sphinx. Słowniki i modele ważą tyle co nic, a działanie nie wymaga dużej mocy od komputera.

PocketSphinx z którego korzystam na filmiku i w kodzie poniżej, waży 6.7 kB!

https://bitbucket.org/dbeef/speechlist/src/990c18c459d5f6b89971fc6b93d24fa4730ba07f/android/libs/pocketsphinx.jar?at=master&fileviewer=file-view-default

Praktyka

Wykorzystanie Sphinxa w przykładzie z filmiku wygląda następująco:

Tworzymy obiekt edu.cmu.sphinx.api.Configuration, aby załadować z plików modele i słowniki.

configuration

Tworzymy obiekt edu.cmu.sphinx.api.LiveSpeechRecognizer, dostarczamy mu konfigurację w konstruktorze i stawiamy warunek który skończy rozpoznawanie mowy (np. while(!lastRecognizedWord.equals(“apple“)), w poniższym przykładzie rozpoznawanie trwa przez cały czas (while(true)).

sphinx2

To wszystko. Teraz, we frontendowej części kodu odczytujemy zapisane przez Sphinx słowa i wyświetlamy na ekranie:

frontend

Cały plik znajduje się pod adresem:
 https://bitbucket.org/dbeef/speechlist/src/990c18c459d5f6b89971fc6b93d24fa4730ba07f/core/src/com/dbeef/speechlist/recognition/SpeechRecognizer.java?at=master&fileviewer=file-view-default

 

Linki:

Repozytorium Speechlist (branch master jest pod rozpoznawanie mowy):

https://bitbucket.org/dbeef/speechlist/src/990c18c459d5?at=master

Artykuł opisujący dostosowywanie CMU pod język polski:

 https://www.researchgate.net/publication/282323232_Tuning_a_CMU_Sphinx-III_speech_recognition_system_for_Polish_language

Dla szukających więcej informacji na temat słowników:

https://cmusphinx.github.io/wiki/tutorialdict/

Mam jednak zastrzeżenie co do ich słów:

There is no need to remove unused words from the dictionary unless you want to save memory, extra words in the dictionary do not affect accuracy.

Z moich doświadczeń wynika, że jest zupełnie odwrotnie. Przekonajcie się sami, zapiszcie sobie kilka słów na kartce, które chcecie wypróbować na Sphinxie, pobierzcie cały słownik z ich strony, wypróbujcie dokładność, a potem zróbcie to samo generując własny za pomocą ich narzędzia, ale wstawiając do niego tylko te słowa, które potem będziecie wymawiać.


dsp2017-1