PiDP-8/I SoftwarePEP001.C
Not logged in

An OS/8 CC8 Implementation of Project Euler Problem #1

The 2017.12.22 release of the PiDP-8/I software distribution includes Ian Schofield's new CC8 compilers for the PDP-8.

That's "compilers," plural, because there is a host-side cross-compiler based on Ron Cain's Small-C compiler that builds and runs on most any system that has a C compiler plus a version that is entirely Ian Schofield's own code which we cross-compile using the host-side compiler, then assemble and link within OS/8 using its built-in SABR and LOADER programs.

We'll start with the OS/8 "native" compiler, then come back and touch on the cross-compiler near the end of this article.

Let us proceed to solve Project Euler Problem #1 using the OS/8 version of CC8.

First Version

The initial public release of CC8 on the PiDP-8/I project mailing list did not support C's modulus operator, %, which is key to the typical solutions for this problem. That lead me to this solution:

int ire0 (n, d)
{
    while (n > 0) n = n - d;
    return n == 0;
}

int main ()
{
    int i, st;
    st = 0;

    for (i = 3; i < 1000; i++) {
        if (ire0 (i, 3) | ire0 (i, 5)) st = st + i;

        if (st > 1000) {
            printf("%d + ", st);
            st = 0;
        }
    }

    printf("%d\n", st);
}

There are many things about this that may seem odd to a knowledgeable C programmer but which have to be that way to work around limitations in CC8:

  1. There are no #include directives for two reasons. First, the OS/8 version of CC8 doesn't currently have a C preprocessor, so it can't use #include directives in the first place. The compiler hard-codes the content of src/cc8/include/*.h rather than require that you #include them directly. Second, if we did have a preprocessor, we'd have different files to #include here than the ones you may expect us to require; see the cross-compiler section below.

  2. CC8 only supports a subset of K&R C, and all types are basically int, so ire0 doesn't bother to define its parameter types.

  3. CC8 doesn't allow you to declare a variable and set it in a single line of code, so we must initialize the st variable after declaring it. The i variable is set by the initialization part of the for loop it controls, so we don't need a separate initialization, but we do need to declare it at the top of main(), because we don't have the freedom of variable declaration the C99 standard gave to C programmers.

  4. The only 2-character operators supported by CC8 are ++, the postfix form of --, and ==. There are several places in the above code where you might expect it to be written in terms of >=, ¦¦, !=, or +=, but we can't use any of those.

    Because we do not require short-circuit evaluation, we can use the bitwise form of the OR operator here instead of the unsupported Boolean form, since in CC8, a Boolean "true" result — as returned by ire0() — is a 12-bit PDP-8 word with all bits set, so that a binary OR with either subexpression returning true gives a true result.

    A related trick would be to make ire0() return 0 or 1 instead of 0 or all-1s, then write the test inside the loop like so:

    if (ire0 (i, 3) + ire0 (i, 5)) st = st + i;
    
  5. CC8 only supports 12-bit arithmetic, so we must use the same subtotaling trick as in my PAL8 solution to this problem.

The ire0 function stands for "integer remainder equals zero," meaning that it returns a true value when the passed divisor d divides evenly into the passed numerator n.

If you add the necessary #include <stdio.h>, this code will build and run correctly on a modern compiler, though you might have to set options that relax its syntax checking to allow K&R style C. If you pipe its output through bc(1), you get the correct answer, which I won't give here to maintain the spirit of the Project Euler challenges.

Building and Running It

This code builds and runs (slowly) on the PiDP-8/I with:

.EXE CCR
>pep001.c

The program will be compiled, loaded, linked, and run by CCR.BI, the "compile C and runBATCH` file that ships with the PiDP-8/I software distribution along with CC8.

(See the companion article Getting Text In for information on getting that pep001.c source code file onto the OS/8 disk.)

Second Version

After sending a distant relative of the above program to Ian Schofield, he made some improvements to the compiler, including adding support for the modulus operator. That allows us to get rid of the ire0() function so:

#include <libc.h>
#include <init.h>

main ()
{
    int i, st;
    st = 0;

    for (i = 3; i < 1000; i++) {
        if ((i % 3 == 0) | (i % 5 == 0)) st = st + i;

        if (st > 1000) {
            printf("%d + ", st);
            st = 0;
        }
    }

    printf("%d\n", st);
}

That version is not only shorter, it runs a lot faster.

Building with the Cross-Compiler

I made two other changes to the above program besides the replacement of ire0() with the C modulus operator, changes which allow the program to build with the cross-compiler:

  1. Added #include directives at the top for the CC8 library definitions and the program initialization code. The OS/8 compiler doesn't need these (nor will it work if you provide them!) because it doesn't have a preprocessor.

  2. Removed int return type from main(). The cross-compiler assumes int returns and will choke if you specify it explicitly, whereas the OS/8 version requires it!

The above program is shipped with the PiDP-8/I software distribution as examples/pep001-mod.c, in the form that the CC8 cross-compiler requires. You can run that file through the bin/cc8-to-os8 filter to produce a version that will build under the OS/8 version of CC8. The same is true for the first version of the program, available as examples/pep001-ire0.c.

Let us then build this second version of the program with the cross-compiler. Starting out at the top of the build tree on a Linux machine after make completes:

$ bin/cc8 examples/pep001-mod.c
$ bin/txt2ptp < examples/pep001-mod.sb > examples/pep001-mod.pt
$ make run
...Loading OS/8...                        ⇠ hit Ctrl-E to get the SIMH command prompt
simh> att ptr examples/pep001-mod.pt
simh> cont
.R PIP
*PEP001.SB<PTR:
^*$                                       ⇠ press Escape twice when ^ appears to exit PIP
.COMP PEP001.SB
.R LOADER
*CC,LIBC                                  ⇠ no /G because we don't want to launch it yet
*$
.SAVE SYS:PEP001.SV                       ⇠ save core image to SYS: volume where R can find it
.R PEP001

There are a number of differences in this example as compared to the previous one:

  1. The method by which we get the C program into the simulated PDP-8 running OS/8 differs considerably. See the companion article Getting Text In for an explanation of the method.

  2. We use the OS/8 COMP command to assemble the SABR file produced by the CC8 cross-compiler instead of executing CCR.BI to compile from C source code. The output of the OS/8 version of CC8 is also SABR, but the COMP step was embedded in the BATCH script. (Ask OS/8 to TYPE CCR.BI to see what it does for you.)

  3. We run the OS/8 linking loader (LOADER.SV) by hand instead of via CCR.BI. That batch file adds the /G/I/O flags, none of which we want here. We don't want /G because we want the program to be linked and loaded but not immediately run. (The "why" is the next step.) We leave off /I and /O because they're not needed here; see the CC8 README.md file for more information.

  4. We ask OS/8 to SAVE the linked and loaded program to disk so that we can run it again later with the OS/8 R command. The CCR.BI method re-builds the program each time you run it that way.

Modern Solution

For comparison, here's how you'd solve this problem in modern C:

#include <stdio.h>

int main ()
{
    int total = 0;

    for (int i = 3; i < 1000; ++i) {
        if ((i % 3 == 0) || (i % 5 == 0)) total += i;
    }

    printf("%d\n", total);
}

There are many things making this program better:

  1. Modern C compilers can be coerced to avoid the need for #include <stdio.h>, but by default, most will insist on it because it allows the compiler to do type checking on external functions like printf(). The better C compilers will even check the types of printf format specifiers for you, where the weaker sort will just try to jam in whatever you passed as parameters. These features prevent whole classes of bugs.

  2. Most C compilers since the K&R '78 era allow declaration and initialization of variables in a single step. I suspect you would have to dig back into the earliest days of Unix to find a version of C as hamstrung as the OS/8 version of CC8. (The CC8 cross-compiler is considerably closer to 1978 K&R C.) This should not be surprising: K&R C was born on a low-end PDP-11, which is still considerably more powerful than a high-end PDP-8/I.

  3. C99 allows declaration of i inside the for loop, which restricts its locality to the loop.

  4. K&R C has the Boolean form of the ¦¦ operator, which makes the key if statement clearer.

  5. K&R C has the += operator, so the total update is a smidge shorter.

  6. The answer requires 18 bits to store, which int in pretty much every modern compiler can hold. Some really old compilers would have required long here instead, but CC8 doesn't support that, either.

Conclusion

Although CC8 is quite limited, even by the standards of early UNIX versions of C, it still supports a useful subset of the language. A short program like the above might take only a fraction of an hour to write, whereas an assembly language version could take days.

On the flip side, the executable for this program takes 6 kB on disk, whereas I was able to write the PDP-8 version in a bit over one page of PDP-8 core, and some clever people on the Internet were able to squeeze it down into one page. (127 bytes!)

Is the tradeoff worth it? It depends on the program.

Other Programs in the Series

I've solved this same problem in many other languages available for the PiDP-8/I:

You may find it interesting to compare their solutions.

License

Copyright © 2017 by Warren Young. This document is licensed under the terms of the SIMH license.