Kategoriarkiv: Hårdvara

Wired gräver efter Bitcoins med hårdvara

(Uppdaterad med länk till artikel om KNCminer.)

I en kommentar till en tidigare postning om bitcoins pekade Robert Andersson på en artikel hos Wired. Wired testar just nu en dedikerad Bitcoin-grävare från Butterfly Labs.

Butterfly Labs Bitcoin-grävare
Butterfly Labs Bitcoin-grävare. En snygg liten maskin.

I artikeln sätter Wired fingret på ett viktigt fenomen med Bitcoin – att det blir svårare och svårare att gräva efter bitcoins. I början räckte det med en vanlig dator. I dag krävs det massiva system av datorer, helst utrustade med kraftiga grafikprocessorer.

Därmed går kostnaden för att gräva upp – både att anskaffa utrustningen och att driva utrustningen, i första hand energiförbrukning. Ett sätt att minska den rörliga kostnaden är att använda allt mer effektiv, dvs specialiserad hårdvara. Det finns i dag både FPGA- och ASIC-baserade bitcoingrävare (Wireds maskin från Butterfly Labs är en sådan maskin). Gizmodo har en artikel som visar lite hur Bitcoin-utrustningen har utvecklats på några få år. Den här gamla utrustningen är inte längre speciellt konkurrenskraftig:

Galet stor Bitcoinmaskin
En system för att gräva Bitcoins som borde ge sysadmin magsår.

Några som håller på och utvecklar FPGA-baserade bitcoingrävare är svenska KnCMiner. Daniel Goldberg och Linus Larsson har skrivit en mycket intressant om KnCMiner och deras maskiner.

Men vad göra för att vara mer effektiv än system med specialiserade Bitcoin ASIC:ar? Lägga kostnaden på någon annan. Tyvärr börjar det dyka upp flera tecken på att Botnets används även för att gräva efter Bitcoins. Tidigare i år fick ett Botnet kallat ZeroAccess gräver efter Bitcoins med hjälp kapade datorer. En synnerligen tråkig om än egentligen inte oväntad utveckling med Bitcoins.

Sedan påpekar Wired och Robert att hela systemet med Bitcoins bygger på säkerheten hos hashfunktionen SHA-256. Och så är det, om vi snabbt kan forcera SHA-256 kommer Bitcoin-systemet att kollapsa. Men då har vi troligen större problem med den digitala säkerheten i vårt samhälle och på Internet än att en digital valuta faller samman.

Matasanos kryptoutmaningar

Det få sätt att effektivt lära sig saker som att faktisk sätta sig ner och praktiskt utföra, öva på den man vill lära sig. Det gäller både saker som kanske är tråkiga, exempelvis glosor på tyska och saker som är desto roligare – spela gitarr eller hacka krypton.

Säkerhetsföretaget Matasano Security har insett detta och har därför skapat en serie spännande krypto och IT-säkerhetsutmaningar. Utmaningarna skickas som mail innehållandes åtta olika problem. Totalt finns sex uppsättningar problem. Problemen sträcker sig från grundläggande kodningar och XOR-krypton till slumptalsgeneratorer, strömkrypton, nyckelsystem och mycket mer. Själva utmaningarna är inte problem avsedda att luras, utan bygger på faktiska attacker och svagheter.

Matasano Security

Jag har precis börjat arbeta mig igenom utmaningarna. För att göra det lite svårare för mig själv försöker jag dessutom implementera mina lösningar inte bara i Python och/eller C, utan även i SystemVerilog. Vi får se hur länge det är realistiskt att göra det. Att implementera RSA i hårdvara kräver en hel del arbete – troligen mer än att lösa själva problemen i utmaningarna. Så här långt har det varit både givande och väldigt roligt.

För mer information om utmaningarna och hur du anmäler dig (du skickar ett mail), se Matasanos sida om utmaningarna. Om du genomför samtliga 48 utmaningar lovar Matasano även att donera 20 USD till välgörande ändamål.

Här finns även en sida skriven av en person som genomfört samtliga utmaningar och berättar lite mer om dom. En krav från Matasano är dock att inte ge beskriva utmaningarna i detalj eller dela med sig av sina lösningar, just för att andra också ska få chansen.

Hacking the Xbox nu som gratis e-bok

Andrew Bunnie Huang, som Secworks tidigare uppmärksammat för sitt projekt att utveckla en egen laptop, har släppt sin bok Hacking the Xbox i PDF-format fri för nedladdning.

Hacking the xbox, som kom 2003 är en fantastisk bok, som inte bara berättar om hur Bunnie som forskarstudent lyckades knäcka skyddet i Xbox. Boken är istället en mycket bra introduktion till metoder och verktyg för att analysera och plocka isär digitala system.

Hacking the xbox

Även om boken har några år på nacken är den fortfarande mycket läsvärd och relativt unik i sitt fokus på praktiskt arbete, inte bara teori.

Skälet till att Bunnie och bokens förlag släpper boken fritt beror på hur hackern Aaron Swartz behandlades. Bunnie skriver bland annat:

No Starch Press and I have decided to release this free ebook version of Hacking the Xbox in honor of Aaron Swartz. As you read this book, I hope that you’ll be reminded of how important freedom is to the hacking community and that you’ll be inclined to support the causes that Aaron believed in.

I agreed to release this book for free in part because Aaron’s treatment by MIT is not unfamiliar to me. In this book, you will find the story of when I was an MIT graduate student, extracting security keys from the original Microsoft Xbox. You’ll also read about the crushing disappointment of receiving a letter from MIT legal repudiating any association with my work, effectively leaving me on my own to face Microsoft.

The difference was that the faculty of my lab, the AI laboratory, were outraged by this treatment. They openly defied MIT legal and vowed to publish my work as an official “AI Lab Memo,” thereby granting me greater negotiating leverage with Microsoft. Microsoft, mindful of the potential backlash from the court of public opinion over suing a legitimate academic researcher, came to a civil understanding with me over the issue.

Här finns hela motivering till varför Bunnie och förlaget släpper boken.

Ny version av SipHash-core med högre prestanda

Den öppna hårdvaruimplementation av den kryptografiska hashfunktionen SipHash som Secworks utvecklat finns nu i en ny version.

I den nya versionen har antalet adderare dubblerats så att den den inre iterationen nu kan utföras på en cykel. Detta gör att antalet cykler för att bearbeta ett meddelande om upp till 8 Bytes (ett block) minskat från 28 till 10 cykler. För långa meddelanden går latenstiden mot 0,5 cykler/Byte.

Storleksmässigt har SipHash-core krympt något och kräver nu Alteras Cyclone IV-teknologi 1088 LE:s, en minskning med 25%. Däremot har maximala klockfrekvensen minskad till 90 MHz. Detta gör att SipHash-core i Alteras teknologi för långa meddelanden kan hantera datatakter på mer än 1 Gbps.

Altera Cyclone IV

Den nya versionen finns i det publika repot för SipHash-core hos Gitorious.

SipHash som öppen hårdvara

Hashtabeller är en av de verkliga arbetshästarna bland datastrukturer. Hashtabeller används bland annat i databaser, i mellanlagring av webbtjänster (webcache), DNS-uppslagningar och inte minst som viktig datastruktur i språk som Perl, Python, PHP, Ruby etc.

Hashtabell där en hashfunktion givet en nyckel skapar index in i tabellen.
Hashtabell där en hashfunktion givet en nyckel skapar index in i tabellen. (Bild från Wikipedi)

En Hashtabell gör det möjligt att givet ett värde (ofta kallad nyckel) direkt få fram ett dataelement. Till skillnad mot exempelvis ett sökträd ger en hashtabell ofta kortare och framförallt konstant tid att lagra och hitta element i strukturen. Detta under förutsättning att inte flera nycklar pekar på samma plats i datastrukturen, ett situation som kallas en kollision. När en kollision uppstår finns det flera strategier för att hantera detta, en är att använda närmaste positionerna i tabellen (uppåt/nedåt om man ser tabellen som en vertikal tabell). Effekten av en sådan strategi är att kollisioner omvandlas till långsam linjär sökning.

En förutsättning för att antalet kollisioner hålls låg är att fördelningen av värden i datastrukturen givet alla möjliga nycklar sker på ett likafördelat sätt. Det vill säga, det är lika stor sannolikhet att en position i tabellen pekas ut som alla andra. Och det som avgör fördelningen i tabellen är hashfunktionen, den funktion som tar en nyckel och räknar ut positionen (även kallat index) i hashtabellen.

Traditionellt har kraven på hashfunktionen varit två:

  1. Den ska ge en likafördelning
  2. Den ska vara snabb

Att den är snabb innebär att den inte kan vara speciellt komplicerad. I min gamla algoritmkursbok, den utmärkta Introduction to Algorihms, är ett av de hashfunktioner som presenteras den här:

Enkel hashfunktion från kursbok.
Enkel hashfunktion från kursbok.

Detta är en enkel och snabb hashfunktion som ger hygglig likafördelning. Nackdelen med den här typen av funktion är att det är enkelt att räkna ut vad en given nyckel ska kompletteras med för att få fram ett givet index. Om en tredje person kan påverka nyckeln in kan denne tvinga fram kollisioner som gör att hashtabellen omvandlas till linjära sökningar som till och med kan sänka en tjänst.

Utslagningsattacker mot hashfunktioner
Ett exempel på detta är den attack på ramverk för webbtjänster som Alexander Klink och Julian Wälde presenterade 2011. Dom kunde visa hur dom med enkel indata kunde sänka kraftiga webbservrar genom att tvinga fram kollisioner i webbplatformens hashtabeller. Författarna demonstrerade fungerande attacker på PHP, ASP.Net, Python, Perl, Java m.m, vilket och ledde fram till utslagningsattacker mot ett stort antal ramverk och applikationer.

Det finns mer avancerade hashfunktioner som försöker kombinera snabbhet, bra likafördelning och samtidigt göra det svårare för den typ av attack som Alexander och Julian visade på. Två av dessa är Cityhash och MurmurHash. Tyvärr har båda dessa funktioner visats sig gå att attackera och räkna ut hur man ska agera för att orsaka en kollision.

Det finns en typ av hashfunktioner som ger ett bra skydd mot attacker av den ovan, och det är kryptografiska hashfunktioner exempelvis MD5 (som dock INTE ska användas) SHA-1 och SHA-256.

Dessa funktioner uppfyller väl kraven på likafördelning och funktionerna ger ett bra skydd mot att tvinga fram kollisioner genom att modifiera nyckeln. Det går helt enkelt inte bestämma vad som skall läggas till nyckeln för att få fram ett givet index (snabbare än att pröva ett enormt antal kombinationer, i fallet SHA-1 är det 2**80 försök). Så vad är då problemet, varför inte byta till en kryptografisk funktion. Prestandan, eller snarare avsaknaden av prestanda.

Kryptografiska hashfunktioner är mycket mer komplicerade än exempelvis Cityhash och består oftast av en funktion som upprepas ett stort antal gånger (kallas iterationer eller rounds). I SHA-1 sker 80 iterationer. Att byta ut hashfunktionerna som använts i exempelvis Python och Perl till SHA-1 anses orealistiskt då det skulle göra hashtabellerna mycket, mycket långsammare och därmed negativt påverka prestandan hos applikationer skrivna i dessa språk

Ett annat problem med de hashfunktioner som använts är att dom är gemensamma för alla instanser. Kan du hitta ett sätt att tvinga fram kollisioner i Cityhash kan du attackera alla system där Cityhash används. Hade hashfunktionen varit unik för varje instans skulle effekten av ett sätt att göra kollisioner blir mycket mindre.

Det vi behöver är alltså en hashfunktion som är:

  1. Mycket snabb, helst inte mycket långsammare än dagens hashfunktioner.
  2. Ger minst lika bra likafördelning
  3. Ger ett starkt skydd mot avsktliga kollisioner
  4. Enkelt går att göra unik för en given instans – program, installation, process

SipHash
En sådan funktion som nyligen presenterades är SipHash, skapad av kryptoexperterna Jean-Philippe Aumasson och Daniel J. Bernstein.

SipHash beter sig mycket som en kryptografisk hashfunktion i det att den iterativt kan beräkna ett värde (kondensat) för ett meddelande genom att tugga i sig meddelandet uppdelat i block med en fix storlek. I SipHash är blocken 64 bitar. Siphash tar även emot en nyckel om 128 bitar som gör beräkningen unik.

Den huvudsakliga operationen i SipHash är SipRound. SipRound består av additioner, logiskt XOR samt bitmässig rotation och dessa operationer appliceras på fyra stycken interna 64-bitars variabler (v0, v1, v2, v3) tillsammans med det givna meddelandeblocket (mi). Figuren nedan visar beräkningskedjan för SipRound:

Beräkningskedjan i SipRound.
Beräkningskedjan i SipRound.

Ringarna med kors är XOR-operationer, kvadraterna är addition och vänsterpilarna är bitmässig rotation. Totalt sker fyra additioner, fyra XOR och fyra rotationer per SipRound.

Att bearbeta ett block sker genom att upprepat applicera ett SipRound ett antal gånger. Efter att alla block har beatbetas sker en avslutande fas där SipRound upprepat applicerat ett antal gånger till. Hur många gånger som SipRound utförs för att bearbeta ett block samt under avslut styr hur säker SipHash är. Skaparna av SipHash har föreslagit Siphash-2-4, vilket innebär två SipRounds för varje block samt fyra SipRounds som avslutning.

Skaparna av SipHash ger i sin artikel som presenterar SipHash motivering till designen hos SipHash, en genomgång av säkerheten samt prestandajämförelser. Enligt skaparna bör SipHash ge ett skydd motsvarande att uttömmande pröva samtliga nycklar till funktionen. Prestandamässigt är SipHash inte mycket långsammare än exempelvis Cityhash och mycket snabbare än MD5. Figuren nedan är från artikeln.

Prestanda för SipHash.
Prestanda för SipHash.

Notera att SipHash prestanda skalar linjärt, till skillnad från MD5 som har en kostsam initieringsfas.

En viktig poäng med SipHash som dess skapare framhåller är att eftersom den har en nyckel och ger kryptografiskt starkt skydd går den även att använda för att beräkna äkthetskoder för meddelanden (Message Authentication Code – MAC) på ett mycket snabbare sätt än exempelvis HMAC. Detta gär SipHash mycket intressant för inbyggda system där äkthetsskydd av meddelanden är mycket viktigt.

Det finns redan i dag ett antal programvaruimplementationer av SipHash och SipHash har även integrerats in i flera projekt projekt bland annat OpenDNS, Perl och Ruby. (Tyvärr har Python ännu inte gjort detta och diskussionen om problemet med kollisioner och hur man vill lösa det i Python är en delvis tråkig läsning.)

Siphash_core
Det som ännu inte funnits är en hårdvaruimplementation av SipHash. Secworks har därför utvecklat en hårdvaruimplementation av SipHash avsedd att integreras i FPGA- eller ASIC-konstruktioner kallad siphash_core. Vår implementation är skriven i relativt konservativ Verilog 2001 och bör vara mycket enkel att integrera. Implementationen är släppt som öppen kod under BSD-licens. Vår implementation av SipHash, siphash_core finns för nedladdning på Gitorious.

Den implementation av siphash_core som finns i dag är en semikompakt lösning där SipRound utförs i fyra steg. I varje steg uppdateras tre eller fyra av tillståndsregistren (v0_reg..v3_reg). Den resursmässigt dyraste operationen är 64-bitars addition och implementationen innehåller två adderare som återanvänds under utförandet av SipRound.

Det skulle gå att göra än en mer kompakt implementation där fler av operationerna använder samma hårdvarurs. En sådan implementation skulle dock knappast ge speciellt mycket bättre prestanda än en programimplementation även på en 16- eller 32-bitars processor.

Det skulle även gå att göra en större implementation där flera av stegen i SipRound utförs i samma cykel. På grund av adderarnas djup är det dock tveksamt om det går att nå speciellt hög klockfrekvens för en sådan lösning. Risken är stor att kostnaden i form av lägre klockfrekvens är större än minskningen i latens.

Vi kommer att testa dessa varianter av implementationer, men känslan just nu är att den version av siphash_core som finns i repot på Gitorious i dag ger bra balans mellan storlek, klockfrekvens och antalet cykler för att processa ett meddelandeblock.

I värsta fallet, för ett meddelande om på exakt 64 bitar krävs det med vår implementation 28 cykler, eller ungefär 3,5 cykler/Byte. Detta kan jämföras med MD5 som kräver minst 64 cykler (om man utför en iteration/cykel) eller 8 cykler/Byte.

Vi har testat att implementera siphash_core i en av Alteras FPGA:er, en Cyclone IV GX. I denna krets kräver siphash_core 1451 LEs (Alteras benämning på sina logiska element) samt 332 register. Inga minnen eller andra resurser används. Den klockfrekvens vi når är 117 MHz. Om vi jämför med den implementation av MD5 som finns på OpenCores så kräver den i samma FPGA-krets 1883 LEs, 910 register och når en klockfrekvens på 62 MHz.

Vi kommer att göra en del modifieringar och utökningar av implementationen. Bland annat kommer vi att som tidigare beskrivit skapa några nya versioner för att täcka in fler designtyper. Vi kommer även att utöka med fler testfall samt ta fram en toppnivåwrapper med ett enkelt 32-bitars gränssnitt som underlättar för integration med WISHBONE eller AMBA.

Om ni har några frågor om SipHash och/eller Secworks implementation siphash_core är det bara att höra av sig.

Bunnie bygger en laptop

Andrew Bunnie Huang, är en av världens mest kända hårdvaruhackers, känd bland annat för att vara den person som hackade Xbox (och skrev en bok om det).

Bunnie
Bunnie

Ett av Andrews senaste kända projekt är att bygga en egen laptop. Laptopen är byggd runt en ARM A9-processor med fyra kärnor. Här är en bild på moderkortet som i dag kan boota upp Linux:

Bunnies moderkort.
Moderkortet, men mååånga portar.

Förutom det man kan förvänta sig av stöd för hårddiskar, minne, tangentbord etc har Bunnies laptop en massa roliga saker som man inte brukar hitta i en vanlig laptop. Här är en lista:

mini PCI-express slot (for blob-free wifi, bluetooth, mobile data, etc.)
UIM slot for mPCIe mobile data cards
Dual-channel LVDS LCD connector (up to QXGA (2048×1536) @ 60Hz resolution) with USB2.0 side-channel for a display-side camera
Resistive touchscreen controller (note: captouch displays typically come with a controller)
1.1W, 8-ohm internal speaker connectors
2x USB2.0 internal connectors for keyboard and mouse/trackpad
Digital microphone
3-axis accelerometer
header for optional AW-NU137 wifi module

External ports:
HDMI
SD card reader
headphone + mic port (compatible with most mobile phone headsets, supports sensing in-line cable buttons)
2x USB 2.0 ports, supporting high-current (1.5A) device charging
1Gbit ethernet

“Fun” features:
100 Mbit ethernet — dual Ethernet capability allows laptop to be used as an in-line packet filter or router
USB OTG — enables laptop to spoof/fuzz ethernet, serial, etc. over USB via gadget interface to other USB hosts
Utility serial EEPROM — for storing crash logs and other bits of handy data
Spartan-6 CSG324-packaged FPGA — has several interfaces to the CPU, including a 2Gbit/s (peak) RAM-like bus — for your bitcoin mining needs. Or whatever else you might want to toss in an FPGA.
8x FPGA-driven 12-bit, 200ksps analog inputs
8x FPGA-driven digital I/O
8x FPGA-driven PWM headers, compatible with hobby ESC and PWM pinouts — enables direct interfacing with various RC motor/servo configurations & quad-copter controllers
Raspberry-Pi compatible expansion header
13x CPU-driven supplemental digital I/Os
3x internal UART ports

Att det sitter en hyggligt stor och kapabel FPGA kopplad direkt till CPU:n öppnar upp för massor med roliga möjligheter, inte bara att gräva efter Bitcoins.

Än så länge finns det inget skal, tangetbord eller skärm så laptopen är just nu ett kort på Bunnies labbord. Men projektet har väckt stor uppmärksamhet och det pratas om Crowdfunding för att ta fram det som behövs för att tillverka färdiga laptops. Och naturligtvis kommer Bunnie att släppa alla designdokument för sin design fri så om inte han själv tar fram en riktig laptop finns det möjligheter för andra att göra det.

Riktigt kul pryl, och inte minst för att labba på eller använda ute i fält för datainsamling skulle den här laptopen kunna vara riktigt, riktigt användbar. Jag vill ha en. Eller två.

Skrämmande snygg kortskimmer

Krebsonsecurity har lagt upp bilder på en kortskimmer som hittats på en bankomat i USA. Skimmern är en helt integrerad lösning som placeras ovanpå bankomatens normala kortlucka.

Skimmern sedd framifrån. Ser seriös ut.
Skimmern sedd framifrån. Ser seriös ut.

Vänder man på skimmern ser man hur den innehåller en läsare för kortets magnetremsa, logik och minne för att genomföra läsningen när kortet passerar och lagra kortets information. Dessutom inkluderar skimmern ett batteri, och kanske mest imponerande en liten hålkamera.

Skimmern sedd bakifrån. Notera läsare, batteri och logik.
Skimmern sedd bakifrån. Notera läsare, batteri och logik.

Kameran sitter på ena kanten av hålet och lyckas tydligen fånga bilder på tangentbordet när PIN-koden slås in. Hålet för kameran är i stort sett omöjligt att se framifrån (jämför med första bilden).

Skimmern sedd från sidan så att kamerans hål syns bättre.
Skimmern sedd från sidan så att kamerans hål syns bättre.

Den här maskinen är antagligen väldigt anpassad till en specifik bankomat där dess fysiska utseende ska se trovärdig ut och inte störa funktionen. För andra automater behöver den anpassas, och i dag är många automater försedda med spikar och liknande för att försvåra att sätta på en skimmer. Men utveckling av skydd och attacker är ett pågående krig och den här skimmern, med imponerande kompakt och väldigt, väldigt skrämmande konstruktion visar hur avancerad denna typ av ekonomisk, elektronisk brottslighet är.

(Fråga: Finns det ett bättre ord på svenska för den här typen av utrustning? Kortläsare känns för generellt.)

Algoritmerna 128-EEA3 och 128-EIA3 godkända av 3GPP

(Det här är egentligen ingen riktigt nyhet då den är flera månader gammal. Men eftersom det inte uppmärksammats tycker jag att det är värt att ta upp.)

3GPPs 53:e SA-möte i september 2011 beslutade 3GPP att anta algoritmerna 128-AAA3 och 128-EIA3 som säkerhetsstandarder för LTE. Länken pekar på agendan/mötesprotokollet från mötet. Den relevanta sektionen att titta på är sektion 11.16.

Vad är nu detta för algoritmer för något? Jo det är de nya konfidentiltets- och integritetsalgoritmerna som skyddar kommunikationen mellan mobilen och mobilstystemet. Dessa algoritmer är byggda runt strömkryptot ZUC. Beslutet som tagits innebär att även ZUC är en antagen standard. (Jag har tidigare skrivit ett par inlägg om ZUC tidigare och även på gamla Kryptoblog.). Strukturmässigt är ZUC ett strömkrypto med en LFSR-kedja sammankopplad med ett tillståndsmaskin – på många sätt likt Snow och Snow3G.

Strukturen hos ZUC.
Strukturen hos ZUC.

Algoritmen 128-EEA3 använder ZUC som en nyckelströmsgenerator. Algoritmen 128-EIA3 är en generator för äkthetskoder (message authentication code – MAC). Algoritmerna kan användas separat eller tillsammans.

I samband med beslutsmötet i september presenterade även ETSIs säkerhetsgrupp SAGE sin slutliga version av sin utvärderingsrapport för ZUC. Rapporten finns att ladda ner (zipfil) från 3GPP.

För den som vill få tag på specifikationerna för ZUC, 128-EEA3 och 128-EIA3 (version 1.6) finns dom att hämta GSMA. På den sidan finns även specifikationer för äldre algoritmer exempelvis Snow3G, Milenage, Kasumi samt deras kryptomoder så som dom används i GSM, 3G, LTE etc. Letar du efter en referensimplementation av ZUC finns den in specifikationen (i dokumentet). Det kan dock vara värt att notera att namnen som används i koden inte riktigt stämmer med de som används i algoritmbeskrivningen. Hos 3GPP själva är den senaste versionen av specifikationerna intressant nog spärrade/censurerade i avvaktan på beslut om exportkontroll. Företaget Galois, som utvecklar verktyget Cryptol har skapat en implementation av ZUC i Cryptol och använt den för att testa algoritmen.

Det ska bli intressant att se utvecklingen runt ZUC, 128-EEA3 och 128-EIA3 – kommer dom att visa sig starka när användningen av dom börjar öka och därmed intresset för att attackera dom ökar? Och kommer algoritmernas användning att få spridning på global nivå.

Bra samling av bithanteringstrick

Vid konstruktion av digitala tekniska lösningar är det inte ovanligt att man behöver göra olika bitmanipulationer och trick med bitar. Detta gäller inte minst inbyggda system med begränsningar i utrymme och prestanda. Alla erfarna konstruktörer har några favorittrix dom tar till för att effektivt lösa ett problem. Typiska trick är kopiering av data i internregister, hitta mest signifikanta biten som är satt i ett ord eller beräkna paritet.

Sidan Bit Twiddling Hacks har den största samlingen av bithanteringstricks jag sett. Det som gör trixen speciellt intressanta är att i stort sett samtliga tricks formellt verifierats med verktyget UCLID. De flesta trick är mest effektiva på en processor med 32-bitars operatorer (och fungerar ofta bra på mindre arkitekturer). Men vissa av dom är avsedda för maskiner med 64-bitars operatorer eller generellt oavsett bitstorlek.

Jag hittade ett bra trick för att beräkna rank parallellt som i hårdvara fungerade riktigt bra. Du kanske också hittar något matnyttigt?

Rita vågformer med Wavedrom

Vid dokumentation av digitala hårdvarukonstruktioner är vågformsdiagram ofta det bästa sättet att förklara timingberoenden och hur protokoll beter sig på cykelnivå. Ett exempel är den här figuren som visar hur en A/D-omvandlare arbetar:

Timingdiagram för A/D-omvandlare.
Timingdiagram för A/D-omvandlare.

Som konstruktör kan det vara svårt att smidigt skapa bra vågformsdiagram att inkludera i dokumentation. En skärmdump från en vågformsvisare som visar testat beteende ökar sannolikheten att diagrammet stämmer med hur konstruktionen fungerar. Samtidigt kan en skärmdump visa för mycket irrelevant information och även bli svårläst vid utskrift etc. Vilka av följande signaler är relevanta att visa för att entydigt förklara funktionen?

GTKwave med en lite mer komplex vågformsdump.
GTKwave med en lite mer komplex vågformsdump.

Man kan alltid rita med olika verktyg. Jag har genom åren använt ett otal ritprogram som Visio, Star/Open/Libre Office Draw, Excel, yED (ett fantastiskt grafverktyg för övrigt) etc. Detta fungerar och kan ge figurer som skalar snyggt och blir bra vid utskrift. Men det är knappast smidigt och effektivt att rita diagram i rena ritverktyg. En variant av att rita diagrammen för hand är att använda ASCII-grafik.

Sedan finns det flera verktyg som går att använda specifikt för att skapa timingdiagram. TimimgTool är ett sådant verktyg som dessutom kan generera en testbänk för konstruktionen utifrån diagrammet (dvs diagrammet kommer först och är sättet du som konstruktör får beskriva din konstruktion). Ett annat liknande verktyg är TimeGen. Slutligen finns det tillägg/makron för att skapa timingdiagram till typsättningsspråket/systemet TeX. Figurerna som genereras ser jättefina ut, men bieffekten är att man måste använda hårbollen TeX…

Timingdiagram genererat med TeX
Timingdiagram genererat med TeX

Sedan ett tag har Google ett kul, fritt (MIT-licensierat) projekt kallat Wavedrom som i mångt och mycket gör det jag vill kunna göra med timimgdiagram. Utifrån en JSON-beskrivning kan Wavedrom generera diagram i form av SVG-bilder. Fördelen med detta är att det går relativt enkelt att, antingen manuellt i en texteditor, eller verktygsmässigt generera JSON-underlaget för diagrammet. Och eftersom utdata är i SVG-format är det lätt att lyfta in i olika textbehandlare och få figurer som skalar bra och ser snygga ut.

Exempel på diagram med Wavedrom.
Exempel på diagram med Wavedrom.

Wavedrom är byggt med Javascript och HTML5 och det är enkelt lägga in Wavedrom-diagram till en webbsida. Det finns även ett tillägg till Chrome som gör att du kan editera Wavedrom direkt i webbläsaren. Så här ser det ut när jag testar med ett exempel:

Test av Wavedrom i Chrome.
Test av Wavedrom i Chrome.

Om du i ditt jobb sitter och ritar timingdiagram och vill hitta mer effektiva sätt att skapa fungerande snygga diagram hoppas jag att du här hittar några bra alternativ – mitt förslag är att testa Wavedrom.