2.4. Filter programmer

Filter programmer er nogen, som læser input og producerer noget output, som for samme input altid vil være det samme. Filter programmer er som skabt til batchkørsel, d.v.s. som jobs, der er automatiserede.

Her kommer det grundlæggende program:

Eksempel 2-13. Simpelt filter, input til output.


/* filter0.c */

#include <stdio.h>

int main()
{
    int c;
    while ( (c=getchar()) != EOF)
      putchar(c);
    return 0;
}

Dette program er så dejligt at eksperimentere med. Når vi har læst vores char med getchar, så kan vi gøre med den hvad vi vil, f.eks. konvertere den fra DOS-tegnsæt til ISO-8859-1 tegnsæt. (Se nedenfor.) Men i første omgang, som her, skriver vi blot vores char ud nøjagtig som vi fik den ind. Hvis nu vi bruger en kommandolinje som nedenfor, kan vi kontrollere, at programmet faktisk kopierer nøjagtigt, d.v.s. at library funktionerne bag vores getchar() og putchar() er ok.


MITPROMPT$ filter0 < /usr/dict/words > words.cpy
MITPROMPT$ cmp /usr/dict/words words.cpy
MITPROMPT$ echo $?
           0
MITPROMPT$ 
# $? er statuskode eller exitcode, som indikerer om
# der er fejl eller ej. 0 betyder ingen fejl, ingen forskelle.

Man kunne tro, at det er uhyre ineffektivt at læse en stor fil et bogstav af gangen, men det er det ikke, hvis vores run-time library ellers er blot nogenlunde godt skrevet. For det første skal det nævnes at getchar og putchar er macroer , derved spares et funktionskald.

For det andet kan man med omdirigering på kommandolinjen bruge sådanne simple programmer til at behandle filer. Det er altså ikke nødvendigt at sidde og taste data ind til sine eksempler.

For at forstå den klassiske konstruktion ((c=getchar()) != EOF) er det en god ide at erstatte (c=getchar()) med c, variabelen, som indeholder det læste bogstav. Så står der:


    while (c != EOF) {
       ...

Et assignment (en tilskrivning, på lokalsproget) har en værdi, nemlig værdien af den sidst foretagne tildeling. Her er der kun en tildeling i udtrykket, så det er meget nemt. Værdien af (c=getchar()) er c.

Læg også mærke til, at det er en int vi bruger til at gemme vores indlæste bogstav. Integer er en datatype, som er større end char. Derfor kan den rumme en værdi, som garanteret ikke er et lovligt bogstav, og det er den, som systembiblioteket indsætter, når der ikke er mere input. Det er som regel -1, og EOF skal være defineret i stdin.

2.4.1. Tegn og talværdier

Lad os først bruge programmet til at skrive bogstavernes talværdi ud i både almindelige titals - notation, i hexadecimal notation, og, hvis bogstavet er udskrivbart, som glyf, eller tegn-repræsentation.

Eksempel 2-14. Filter, som skriver ascii ordinal value.


/* char2tal.c */

#include <stdio.h>

int main()
{
    int c;
    while ( (c=getchar()) != EOF) {
      printf("Decimal-værdi %3d, hexadecimal værdi 0x%2x ", c, c);
      if (c > 31 && c < 127)
          printf("%c\n", c);
      else
          printf(".\n");
    }
    return 0;
}

Dette program producerer noget output, som indeholde alle de samme informationer som den oprindelige fil. Den indeholder endda flere informationer, skønt ikke så mange som den kunne.

Vi har med dette program mappet input til output på en måde, så vi ikke har tabt data. Vi kan skrive et program, som ud fra outputfilen rekonstruerer den oprindelige fil.

Der er også en anden sjov ting ved programmet: Hvis vi skulle sende data over et ustabilt transmissionsmedium, så ville det være nemt at finde de linjer, hvor data var gået tabt. I mange tilfælde ville man ved mindre fejl endda kunne regne det rigtige input ud. Denne form for overskud af bits til at repræsentere data kalde redundans. "Redundancy" oversættes i ordbogen til overflødighed, men vi kunne også oversætte det til "rigelighed", "med ekstrareservebits som forsikring ..." (Bedre forslag modtages med glæde!)

Som en biting til C++ interesserede kan det tilføjes, at man i C++ nok også ville slippe nemmere afsted i dette tilfælde ved at bruge printf. C++ cout() er ikke så nem at bruge til formatering af kolonner og lignende.

Lad os dernæst bruge programmet til at tælle characters.

Eksempel 2-15. Simpelt filter som character counter.


/* filter1.c simpelt filter tæller chars istf at ouputte. */

#include <stdio.h>

int nc;

int main()
{
    int c;
    while ( (c=getchar()) != EOF)
      ++nc;
    }
    printf("%d\n", nc);
    return 0;
}

Hvorfor initialiseres nc ikke? Jo, for det er en global variabel, og den er garanteret zeroed out. Al global hukommelse, som ikke er explicit initialiseret, er garanteret en nulstilling. Man kan selv gøre det, i øvrigt, hvis man har en snavset buffer: memset(buf,0,lengde);

Et eksempel på en kørsel af programmet:


MITPROMPT $ time charcount < /usr/dict/words
409048
    0.32s real     0.27s user     0.04s system

På min gamle maskine, 3/10 sekunder til at læse 400KB! Det er pænt (i forhold til maskinens formåen). Den "officielle" wordcount, wc < /usr/dict/words er dog 10 gange hurtigere!

Husk at denne charcount ikke tæller bytes, men bogstaver. På en linux maskine er dette normalt det samme. På et MicroSoft system vil længden af filen ikke svare til antal characters talt på denne metode, fordi MicroSoft operativsystemer (og andre) benytter carriage-return line-feed sekvenser til linjeskift. Når man kører "normal C" - eller simpel, POSIX-C - på en platform som MS-OS'erne, så filtreres alle cr - tegn fra.

For at se alle ascii koder kan du benytte man kommandoen:


PROMPT $ man ascii
[...]
PROMPT $ man groff-char

2.4.2. Et typisk filter

Et filterprogram, som svarer til den normale anvendelse af ordet filter, er et program som kan konverterer CodePage 865 til ISO-8859-1. Det kan gøres på forskellige måder, men eksemplet egner sig godt til at demonstrere, hvordan man "mapper" en datamængde over i en anden.

Lad os for simplicitetens skyld gå ud fra, at hvert bogstav er en byte. (Desværre er jeg ikke klar over, om iso8859-1 altid er en byte, men det går vi altså ud fra, at de er.) Vi skal med andre ord kunne konvertere en byte til en anden byte. Antallet af mulige værdier i begge lejre er kun 256.

Den hurtigste teknik til en sådan opgave er derfor tabelopslag, som kan svare på, hvilken ny værdi vores byte skal have ved at bruge vores input som index i et array med 256 værdier.

For at prøve teknikken lader vi først en loop initialisere arrayet først, således at der ingen konvertering ville finde sted. Derefter prøver vi, om vores program kopierer input til output uden ændringer.

Eksempel 2-16. Codepage 865 til iso8859-1, forstadium.


/* ibm2iso0v1.c, forstadium til konverteringsprogram 
 * Codepage 865 -> iso8859.1
 */

#include <stdio.h>

static char conv[256];

int main(int argc, char *argv[])
{
    int c;
    int jj;

    for (jj = 0; jj < 256 ; ++jj)
        conv[jj] = jj;

    while ( (c=getchar()) != EOF) 
        putchar(conv[c]);

    return 0;
}

Somme tider klager folk over, at C programmet ikke har boundary tjek for arrays. Det er der selvfølgelig den gode grund til, at det ville være spild af tid i et godt program. Hvorfor vil ovenstående program ALDRIG gå ud over grænserne fra 0 til 256?

Hvordan tester man nu sådan et program? Her er Unix suverænt, man omdirigerer input fra en fil og samler test output op i en anden fil. På den måde opnår man, at selve test-proceduren kan automatiseres (evt. sættes ind som et target i en makefile.)


fri2c:  gcc -Wall ibm2iso0v1.c -o ibm2iso0v1
fri2c:  ibm2iso0v1 < textfile > textfile.kpi
fri2c:  cmp textfile textfile.kpi


Den næste terrasse, som vi vil nå op på, skal konvertere et enkelt tegn og lade resten være. Vi benytter derfor stadig loopen, men tilføjer nu en linje, som ændrer en enkelt af tabelværdierne, og ser, om vi får det ønskede resultat, hvis vi sender input af den pågældende værdi. (Det gør vi selvfølgelig).

Eksempel 2-17. Terrasse 2


/* ibm2iso0v2 - forstadium 2, konvertering af en enkelt værdi. */

#include <stdio.h>

static char conv[256];

int main(int argc, char *argv[])
{
    int c;
    int jj;

    for (jj = 0; jj < 256 ; ++jj)
        conv[jj] = jj;

    conv['A'] = 'a';                  /* Ja, man må gerne! */

    while ( (c=getchar()) != EOF) 
        putchar(conv[c]);

    return 0;
}

Når man kører ovenstående program (fra kommandolinje, med inddata fra tastaturet) skal man få lille a hvis man taster store a. Ellers skal alt output være det samme som input.

Den version af programmet, som vi slutter med her, behøver ikke at være den endelige version. De mange sjove grafiske tegn, som findes i codepage850 og 865 kan man jo forestille sig efterlignet på mange måder, afhængig af, om man skal ud på en printer eller en ascii skærm eller en grafisk tegneflade (stort arbejde!). Vi nøjes med en version, som konverterer de danske tegn i IBM-tegnsættet codepage 850 til ækvivalenterne i iso8859-1.

Eksempel 2-18. Terrasse 3


/* ibm2iso.c - terrase 3, konvertering af danske tegn. */

#include <stdio.h>

static char conv[256];

int main(int argc, char *argv[])
{
    int c;
    int jj;

    for (jj = 0; jj < 256 ; ++jj)
        conv[jj] = jj;

    conv[134] = 'å';              /* 134 er codepage850 for å */
    conv[143] = 'Å';              /* 143 er codepage850 for Å */
    conv[145] = 'æ';
    conv[146] = 'Æ';
    conv[155] = 'ø';
    conv[157] = 'Ø';
    conv[130] = 'é';
    conv[144] = 'É';
                                  /* fortsæt listen efter behov */

    while ( (c=getchar()) != EOF)
        putchar(conv[c]);

    return 0;
}

Den teknik, som er vist her ovenfor, er selvfølgelig lidt for nem. Hvis man vil have en lynhurtig service ved hjælp af en opslagstabel, skal tabellen selvfølgelig være initialiseret i forvejen. Det må man med andre ord skrive i hånden:


char ctab[256] = 0,1,2,3, /* nej ikke stop her! */

Det er den teknik, som anvendes i library funktionerne isprint(3), isdigit(3), toupper(3) osv. fordi det simpelthen er den hurtigste måde. Hver konvertering koster kun en enkelt indexerings-operation - især hvis funktionerne er erklæret som inline funktioner (findes i gcc og er med i den nye standard C99).

2.4.3. Oversætter - teknik, forstadium

Ud over de grundlæggende typer tekstfiltre, som vi har set på her, ville det være nyttigt at se et par eksempler på programmer, som kan filtrere mime-kodede postfiler.

Denne gang nytter det ikke at lave byte til byte mapning. Vi har som input sekvenser, der begynder med et lighedstegn og fortsætter med en hexadecimal talværdi for det ønskede output tegn. Fx. vil i "blåbærgrød" i Mime-kodning blive skrevet således: bl=e5b=e6rgr=F8d. Det er klart en forbedring at få det oversat til noget, som ligner de danske tegn noget mere. Desuden kan man bruge Mime-kodning til at angive et linjeskift, der ikke skal med i den færdige tekst. Meget rart, hvis man har problemer med lange linjer i fx. en mail transport agent. Det gøres ved at afslutte linjen med et lighedstegn.

Her kommer først en simpel version, som kun kan operere i en kanal (på engelsk en pipe), d.v.s. den læser fra stdin og skriver til stdout. (Med programmer til kommando fortolkeren bash eller ksh, kaldet shell scripts, kan man klare fil-opsætning for alle andre situationer, så det er såmænd ikke så ringe endda!)

Eksempel 2-19. mime afkodning, std.input


/* mime2asc.c - konvertering af mime - koder til ascii. */

#include <stdio.h>

static char str[3];

int main(int argc, char *argv[])
{
    int c, c2;
    char *ptr;

    while ( (c=getchar()) != EOF) {
        if (c != '=')
            putchar(c);
        else {
            if ( (c2 = getchar()) == '\n')  /* aha! linjen ønskes ikke brudt */
                continue;                   /* print ikke ny-linje-tegn */
            else {
                if (feof(stdin)) exit(1);
                str[1] = getchar();
                if (feof(stdin)) exit(1);
                str[0] = c2;
                c = strtol(str, &ptr, 16);
                putchar(c);
            }
        }
    }

    return 0;
}

Programmet er uhyre simpelt i forhold til en produktionsversion, men indeholder det nødvendige for at fremhæve pointen. Håndteringen af End-Of-File er klodset, og fejl ved konvertering af de to tegn efter lighedstegn håndteres slet ikke. EOF håndteringen kunne håndteres ved at benytte en linjebuffer og fgets(), og strtol(3) giver os et errno, som vi kunne tjekke på.

Vi benytter os af det faktum, at ethvert '=' skal forstås på en speciel måde, det indleder en mime sekvens. Det kan man kalde for et meta tegn, et tegn, som ikke blot er et tegn. Det er en kommando, på samme måde som '\' er en speciel kommando i en C string, '\n' betyder newline og ikke bogstavet n.

Hver gang vi støder ind i et tegn, undersøges, om det er et lighedstegn, og hvis ikke går det ufiltreret til output.

Lighedstegnet smides væk og de to næste characters puttes i en streng, der bliver opfattet som en hexadecimal værdi. Denne konverteres ved kald til strtol(3) string to long. Denne fornemme konverteringsrutine får en pointer til stringen med hexadecimal tallet, adressen på en character pointer, som den så kan bruge til at rapportere, hvor meget den kunne konvertere, og endelig et tal, som er radix for konverteringen, d.v.s. at hvis vi vil konvertere et almindeligt tal, skal vi aflevere et 10-tal her.

strtol(3) kunne godt undvære parameter 2, eller rettere, vi kunne fortælle den, at der ikke er nogen pointer ved at aflevere en NULL pointer. strtol(str,NULL,16);

strtol ville returnere et 0, hvis de efterfølgende bogstaver ikke kan konverteres, og det ville selvfølgelig være en situation, vi burde undersøge nøjere, ligesom errno, en static variabel i library modulet, burde tjekkes. Prøv at gøre det, og giv programmet input med fejl i og kontroller, at programmet håndterer det på en fornuftig måde!

Lad os til sidst forbede programmet, så det selv kan finde ud af at åbne filer, konvertere indholdet og skrive resultatet ud i en fil med et andet navn.

Eksempel 2-20. Mime afkodning, fil input


/* mime2ascii.c - fil konvertering af mime - koder til ascii. */

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

void konverter(FILE *infil, FILE *outfil);

int verbose;            // global flag

void error(char *message, int exitcode)
{
    fprintf(stderr,"%s\n",message);
    exit(exitcode);
}

#define MAXNAME 512

int main(int argc, char *argv[])
{
    FILE *fp, *nyfilp;
    char nyfilnavn[MAXNAME];
    char errormsg[MAXNAME+80];
    int j=0;

    while (++j < argc) {
        if (argv[j][0] == '-')
            switch(argv[j][1]) {
                case 'v': verbose=1;
                          break;
                default: error("Option ikke forstået", 40);
            }
    }
    j=0;
    while (++j < argc) {
        if (argv[j][0] == '-')
            continue;
        if (strlen(argv[j]) > MAXNAME - 2)
            error("Filnavn er for langt", 100);
        fp = fopen(argv[j],"r");
        if (!fp) {
            sprintf(errormsg, "Kan ikke åbne fil ved navn %s",argv[j]);
            error(errormsg,2);
        }
        strcpy(nyfilnavn,argv[j]);
        strcat(nyfilnavn,".X");
        nyfilp = fopen(nyfilnavn,"w");
        if (!nyfilp)
            error("Kan ikke åbne fil for skrivning",103);
        if (verbose)
            fprintf(stderr,"Har åbnet %s, starter konvertering\n", argv[j]);
        konverter(fp,nyfilp);
    }
    return 0;
}

void konverter(FILE *fil, FILE *outfil)
{
    int c, c2;
    char *ptr;
    static char str[3];

    while ( (c=getc(fil)) != EOF) {
        if (c != '=')
            putc(c,outfil);
        else {
            if ( (c2 = getc(fil)) == '\n')  /* aha! linjen ønskes ikke brudt */
                continue;                   /* print ikke ny-linje-tegn */
            else {
                if (feof(stdin)) exit(1);
                str[1] = getc(fil);
                if (feof(stdin)) exit(1);
                str[0] = c2;
                c = strtol(str, &ptr, 16);
                putc(c,outfil);
            }
        }
    }
}

En kommandolinje, som består af 3 ord, fx. mime2ascii fil1 fil2 vil blive opdelt i de tre ord, altså "mime2ascii" er det første, "fil1" er det andet, "fil2" er det tredie ord.

argc er sat til 3 af den startup kode, som sætter vores program i gang. argv[0] er derfor ordet "mime2ascii", det vil sige vores eget programs navn. Da vores program altid har et navn, er argc altid mindst 1. Man gemmer sommetider programnavnet i en global character-pointer, fx. således:

 
char *thisprog; 
main(int argc, char *argv[])
{
    thisprog = argv[0];
    /* mere program ... */

Hvis man skal have fat i sidste ord på kommandolinjen er det altså argv[argc-1] - Husk, at array elementer starter med 0, d.v.s. første element er argv[0].

For at vise, hvordan main får argumenterne fra kommandolinjen, kan man lave en "terrasse1" af dette program, hvor man nøjes med at løbe argumenterne igennem og skrive dem ud på skærmen.

Læg mærke til, at programmet gennemløber kommandolinjen 2 gange. Første gang er det blot for at få de eventuelle options. Vi har lavet en enkelt optionmulighed, nemlig -v for verbose. Det fungerer - men det er en meget rå form for kommandolinje analyse. Vi vil i andre eksempler vise flere måder at gøre dette.

Alt i alt er mime2ascii dog betydeligt mere praktisk end forgængeren. Det læser de filer, som man angiver på kommandolinjen, og skriver det konverterede indhold ud i en fil med samme navn med en tilføjelse af ".X".

Det kunne lige så godt være en anden endelse, og det står dig selvfølgelig frit for at ændre programmet til at lave filer, som ender på .txt. Nogle gange vil man måske ønske, at man sletter den oprindelige fil (eller gemmer den under et andet navn) og omdøber (renamer) den konverterede fil til det oprindelige filnavn. Dette er en god ide, hvis mime2ascii aldrig laver fejl! Det vil være en god opgave til programmeringsarbejde at polere dette filter, således at det fungerer perfekt og selv genererer fornuftige filnavne.

I afsnit Afsnit 2.5 udvidedes denne programtype, så den kan håndtere lidt længere sekvenser af tegn, således at man kan analysere input på et lidt højere abstraktionsniveau.

2.4.4. Summering af tal i en fil.

Et program, som ønsker at behandle linjer i st.f. characters, kan optimere IO ved at benytte fgets(2). Vi kan benytte denne funktion til at skrive et program, som læser en fil med tal og lægger dem sammen og skriver resultatet. Det er fascinerende at se et program, der kan behandle en megabyte datafil på brøkdele af et sekund.

Allerede nu kan det forudses, at hvis den kan "forstå" negative tal også vil kunne trække fra.

Der findes situationer fra det virkelige liv, hvor sådan et program kunne være nyttigt. Hvis vi f.eks. har foretaget et udtræk fra en stor database med alle telefon taksttelegrammer fra lørdag 24.00 til søndag 06.00, så kan vi beregne den samlede tid og hvor meget det ville koste at give natterabat. Men også datafiler fra alle mulige andre situationer ville kunne være input. Normalt vil man på Unix klare den slags med awk, men hvis man skulle optimere (f.eks. p.g.a. store datamængder fra en telefoni-data), så kunne det blive aktuelt at skrive det rå C program.

Pseudokode er måden at programmere på, hvis man ikke er interesseret i sprogets finurligheder, men blot ønsker at forklare mekanikken i et program. Vores fil-additionsmaskine vil i pseudokode se ud nogenlunde sådan her:


Så længe der er linjer,
  læse næste linje,
  konverter linjen til et tal, hvis muligt
     er det ikke et tal, så vis linjenr, linje og gå ud;
  læg tallet til totalen.
Print totalen.

Programmet er så simpelt, at vi skriver det i et hug.

Eksempel 2-21. Filter som konverterer linjer med tal til summen af tallene.


/* summer.c */

#include <stdio.h>
#include <stdlib.h>   /* for string to double, strtod() */
#define MAXL 80000
int main()
{
    char line[MAXL];   /* for input */
    char *ptr;         /* for strtod konverteringspointer */
    double tal;        /* for det laeste tal */
    double sum = 0;    /* for totalen */

    while ( (fgets(line,MAXL,stdin)) != NULL) {
        tal = strtod(line,&ptr);
        sum += tal;
    }
    printf("%18.2f\n",sum);
    return 0;
}
/* end of file summer.c */

strtod(3) (STRing-TO-Double) er en funktion, som konverterer en string til double. Denne funktion er mere avanceret end atoi, i det den kan sætte en fejl-variabel, hvis konverteringen ikke lykkes, og den kan flytte en pointer hen ad tekst strengen til det første bogstav, der ikke kunne konverteres. Man kan også bruge den på en mere simpel måde; man giver den blot NULL som anden parameter, og krydser fingre og siger: det skal nok gå alt sammen ...