Programmeringsmetodik: Inlämningsuppgift 1, "Digsim"

Den här uppgiften går ut på att lära sig, och visa att man förstått, modularisering och abstraktion. (Det är samma som inlämningsuppgift 1 förra året.)

Specifikation

I processorn på en dator brukar det finnas en ALU, en aritmetisk-logisk enhet, som utför beräkningar med hjälp av bitar som skickas genom grindar i en elektronisk krets. Vi ska simulera additionsdelen av en ALU genom att skriva ett program som utför addition av heltal (positiva och negativa) i binär form med hjälp av digitala grindar, som programmet ska simulera.

Programmet ska läsa in två heltal (till exempel 17 och 19), och omvandla dessa till binär form, i form av bitsträngar (som 00010001 och 00010011). Sen ska det addera bitsträngarna till en summasträng, och slutligen omvandla summasträngen tillbaka till ett heltal och skriva ut det (36).

För att kunna hantera tal med olika antal bitar (till exempel 8-bitarstal, 16-bitarstal och 64-bitarstal) ska programmet börja med att läsa in antalet bitar i bitsträngarna, och strängarna ska sen skapas dynamiskt. (Det kommer dock att finnas en begränsning i hur många bitar vi kan hantera, eftersom vi läser in och skriver ut talen med hjälp av vanliga heltal, alltså datatypen int.)

För att avbilda negativa heltal används tvåkomplementmetoden.

Det krävs ingen hantering av overflow, alltså då antalet bitar inte räcker till. Med "ingen hantering av overflow" menar jag att man bara låter det bli det bitmönster som blir, med det angivna antalet bitar, även om det blev overflow och negativt. Man ska ju simulera en ALU, så jag tycker att det ska funka som i en riktig processor, och har man en ALU med fyrabitarstal som representerar negativa tal med tvåkomplementmetoden, så kan den representera talen -8 (1000) till 7 (0111) Om man lägger ihop 4 och 4, så kan resultatet (8) inte lagras, utan det blir overflow och man får svaret -8.

Programmet ska byggas i moduler enligt figuren:

Försök separera modulerna ordentligt, så koden i en modul inte blir onödigt hopvävd med koden i en annan!

Modulen "Bit"

Modulen Bit ska hantera den abstrakta datatypen "bit", alltså en binär siffra, 0 eller 1, Modulen innehåller funktioner på bitnivå för de enkla digitala grindarna (and, or och så vidare), samt för en bitadderare. Vi låter för enkelhets skull 0 representeras av tecknet (en char i C) '0', och 1 av tecknet '1'.

Så här ser specifikationsfilen Bit.h ut:

/* Bit.h */

char and(char a, char b); /* Returnerar '1' om a '1' och b '1' */
char or(char a, char b);   
char xor(char a, char b);
char not(char a);
char nand(char a, char b);
char nor(char a, char b);

void add(char a, char b, char ci, char *sum, char *cu); 
/* Adderar två bitar a och b med ci som in-carry och cu som ut-carry enligt figur */

Modulen "Bitstr"

Modulen Bitstr ska hantera den abstrakta datatypen "bitsträng", alltså ett helt binärt tal bestående av flera ettor och nollor. En bitsträng representeras av en vanlig C-sträng (en array av char), innehållande bitar (tecknen '0' och '1').

Så här ser specifikationsfilen Bitstr.h ut:

/* Bitstr.h */

void addstr(char *astr, char *bstr, char *sumstr);
/* Adderar astr och bstr till sumstr */

void twokomp(char *str);
/* Tvåkomplementerar str */

Modulen "Omvandla"

I den här modulen har vi samlat funktioner för omvandling mellan vanliga heltal och bitsträngar.

Så här ser specifikationsfilen Omvandla.h ut:

/* Omvandla.h */

void tal_str(int tal, char *str, int nrbits);
/* Omvandlar tal till en binär sträng med nrbits bitar */

int str_tal(char *str);
/* Omvandlar den binära strängen str till ett heltal */

Modulen "Digsim"

Det här är huvudprogrammet, som upprepat (avsluta med 0) läser in antal bitar som ska användas, och dynamiskt allokerar så långa strängar för den binära formen. Programmet ska sedan läsa in de båda heltalen, skriva ut deras binära representation, utföra additionen och skriva ut summan både i binär form och som heltal. (Glöm ej att strängarna ska ha plats för '\0'-tecken, och att avallokera minne.)

Några tips

Jobba "bottom up". Börja med en modul "längst ner", dvs en som inte använder några andra moduler, utan bara används av andra. I vårt fall är det modulen Bit. Testa varje modul för sig innan du går vidare med nästa. (Repetera gärna uppgift 1 och 3 i C-programmeringskursen!)
Bygg först hela systemet för bara positiva tal, och komplettera sedan för negativa tal.

Här är föreläsningsanteckningarna från Gunnar Jokis presentation av digsim-uppgiften. Klicka på bilden för större format.

Extrauppgift

(Ej obligatoriskt)

Komplettera modulen Bitstr med en funktion för multiplikation av binära strängar, och komplettera huvudprogrammet med multiplikation av heltal.

Redovisning

Redovisning sker genom att programmet uppvisas och provkörs för labbhandledaren. Skicka också in källkoden med mail till labbhandledaren.

Om samarbete på inlämningsuppgifterna: Varje grupp (som normalt består av en eller två studenter) ska göra en egen lösning, och skicka in den, men det är inte förbjudet att samarbeta eller fråga andra studenter om hjälp. Däremot ska man i så fall tydligt ange vilka som man samarbetat med. Varje lösning måste ange namnet på alla som bidrog i arbetet. Samarbete är alltså tillåtet, men måste redovisas.

Godkänd redovisning utgör en del av delkurs 2 i kursen Programmeringsmetodik.

Inlämningsuppgifterna bör göras, och lämnas in, före tentan. Man får tenta utan att ha lämnat in uppgifterna, men:

Innan man gjort uppgifterna kan det vara svårt att klara tentan.
Eftersom betyget på hela kursen sätts efter tentaresultatet, får man kanske ett betyg som inte motsvarar de kunskaper man får efter att ha gjort uppgifterna.
Efter tentan är kursen egentligen slut, och vi prioriterar därför inte rättningen av uppgifterna. Uppgifter som lämnas in då hamnar underst i prioritetshögen. I värsta fall blir de inte rättade förrän nästa gång kursen går.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 15 september 2011