Quiz 9: Caesar cipher

Write a program in assembly that behaves as follows:

• The user can type in some message on stdin (standard input) and can terminate the message with the end of file condition (Control-D).

• The program reprints the message character by character. Like the cat program. However, the characters a, .., y, z are replaced with b, ..., z, a. That means the characters a to y are replaced with the next character in the alphabet, and z is replaced with a.

  All other characters (e.g. upper case characters and punctuators) are reprinted unchanged.

Take advantage of the fact the in the ASCII table the characters a, .., z come in alphabetical order.

With some Unix magic you also can write a message first into a file:

1
2
3

abcdefghijklmnopqrstuvwxz
Hallo, Welt!
hello, world!

and then redirect the file to stdin:

theon$ 1_ulm_build/caesar/ulm a.out < msg
bcdefghijklmnopqrstuvwxya
Hbmmp, Wfmu!
ifmmp, xpsme!
theon$ 

Required Instructions

Use the table for Ordered Relations (Session 5, Page 3) to provide the following instructions for conditional jumps:

• ja (jump above) with opcode \(0\text{x}0C\). It can be used to branch if \(u(a) > u(b)\). The branch condition therefore is that a previous subtraction \(u(a) - u(b)\) was negative.

  Example usage:

  1 2 3

  getc %1 # read character (its ASCII code) from stdin subq 'z', %1, %0 # compute: %1 - 'z' -> %0 ja not_in_range # jump if char in %1 comes after 'z' in ASCII table

• jb (jump below) with opcode \(0\text{x}0D\). It can be used to branch if \(u(a) < u(b)\). The branch condition therefore is that a previous subtraction \(u(a) - u(b)\) was positive.

  Example usage:

  1 2 3

  getc %1 # read character (its ASCII code) from stdin subq 'a', %1, %0 # compute: %1 - 'a' -> %0 jb not_in_range # jump if char in %1 comes before 'a' in ASCII table

Together with the instructions from Page 2 this is sufficient to realize the program. If you think more instructions are needed or would make it more convenient feel free to add more.

Getting Started

The right approach would probably be to figure out the perfect algorithm, represent it in a flow-chart and then implement.

Here I outline some hacker's approach where you approach the goal step by step. And each step will be expressed with some code that you can use as some kind of pseudo-code (but it actually compiles into an executable and solves some part of the problem).

After each step test it. So although you do not come up with the solution in a single step it will be a safe path.

First Step

Use the cat program. It already does everything, well, except for replacing the characters. In C coode you could express the cat program like that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <stdio.h>

int
main()
{
    int ch;

    while ((ch = getchar()) != EOF) {
        putchar(ch);
    }
}

Here the test:

theon$ ucc -o caesar0 caesar0.c
theon$ caesar0 < ../caesar/msg
abcdefghijklmnopqrstuvwxz
Hallo, Welt!
hello, world!
theon$ 

Second Step

Now modify your assembly program by incrementing the stored ASCII code before you print it. So this replaces all characters with the next character in the ASCII table. So some characters are already replaced correct.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <stdio.h>

int
main()
{
    int ch;

    while ((ch = getchar()) != EOF) {
        ++ch;
        putchar(ch);
    }
}

Here the test (note that the newline also gets replaced):

theon$ ucc -o caesar1 caesar1.c
theon$ caesar1 < ../caesar/msg
bcdefghijklmnopqrstuvwxy{Ibmmp-!Xfmu"ifmmp-!xpsme"theon$ 

Third Step

Only replace characters a to z with the next character. So except for z all characters are replaced correct.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <stdio.h>

int
main()
{
    int ch;

    while ((ch = getchar()) != EOF) {
        if (ch >= 'a' && ch <= 'z') {
            ++ch;
        }
        putchar(ch);
    }
}

Here the test (now the newline and punctuators are unchanged):

theon$ ucc -o caesar2 caesar2.c
theon$ caesar2 < ../caesar/msg
bcdefghijklmnopqrstuvwxy{
Hbmmp, Wfmu!
ifmmp, xpsme!
theon$ 

Last Step

Now deal with the special case that z should be replaced with a.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <stdio.h>

int
main()
{
    int ch;

    while ((ch = getchar()) != EOF) {
        if (ch == 'z') {
            ch = 'a';
        } else if (ch >= 'a' && ch <= 'z') {
            ++ch;
        }
        putchar(ch);
    }
}

Here the test:

theon$ ucc -o caesar3 caesar3.c
theon$ caesar3 < ../caesar/msg
bcdefghijklmnopqrstuvwxya
Hbmmp, Wfmu!
ifmmp, xpsme!
theon$ 

Now, it is a matter of taste to replace ch <= 'z' with ch < 'z' ...

Submission for Quiz 8

Submit your description of the instruction set isa.txt and your program caesar.s with submit hpc quiz08 isa.txt caesar.s.