ioccc/1992/buzzard.1/README.md

## To build:

``` <!---sh-->
    make all
```


## To use:

``` <!---sh-->
    ./buzzard.1 num num
```


## Try:

``` <!---sh-->
    ./try.sh
```


## Judges' remarks:

To see good C Preprocessor buzzard.1, try:

``` <!---sh-->
    make babble.cppcb
    cat babble.cppcb
```

Notice how many statements it takes to do anything useful?


## Author's remarks:

### What you shouldn't think about `buzzard.1`:

`buzzard.1` doesn't just do a mass of `#define`s as its obfuscation.


### What you should be glad about:

I didn't just submit the post-C-preprocessed output as an entry.


### Cute trick warning

`buzzard.1` contains only a numeric `printf(3)`, yet sometimes it prints out
short strings.


### What it does

`buzzard.1` is a simple mathematical program. It expects two numeric
arguments.

``` <!---sh-->
    ./buzzard.1 0 <num>
```

will print out the factorial of `<num>`.

``` <!---sh-->
    ./buzzard.1 <num1> <num2>
```

will print out the largest common factor of `num1` and `num2`.

``` <!---sh-->
    ./buzzard.1 1 <num2>
```

will print out a factor of `num2` if it's composite, or else
it will print a string informing you that `num2` is prime.

If the first argument is less than 0, it prints out an
error message.


### What it is

`buzzard.1` is a translator from a pseudo-assembly language into a subset of C
suitable for execution on Charles Babbage's Analytical Engine.  Or rather, the
`#define`s in `buzzard.1` are that translator.  The rest of `buzzard.1` is a
`buzzard.1` program.  If you run the whole mess through CPP and a beautifier, you
will see that all you have is a loop that runs until a variable is not 0, and a
sequence of assignment statements.  The assignment statements are all of the
form `a op= b` or `a = b`.  The Engine actually allowed 'a = b op c'.  Only `+`,
`-`, `/`, and `*` are used--no boolean or bitwise operators.  The infinite loop
could have been simulated on the AE by connecting the already-processed card
stack to the input card stack.


### How to try to understand it

*Don't* expand the `#define`s!  Rather, decipher what they do.
Some of them are mere obfuscation fodder, put in to encourage
you to run it through CPP.


### What it doesn't do quite right as an emulator

Because of the definitional constraints, calls to `atoi(argv[#])` also appear
inside the loop.  These could be put outside--the initial values of the
"registers" on the AE--but the macro conventions being used didn't lend
themselves to it.


### Theoretical observations

The simulated comparison operations only work with a certain range of numbers;
numbers that are too large will cause the output code to fail to simulate the
input code.  This means that this implementation of `buzzard.1` would not be
Turing-complete, even if the AE could process indefinitely-sized numbers.
However, this is actually a constraint that no actual computer can meet, either,
so we can conclude that if an AE, with card bins connected as suggested above,
were hooked up to a memory unit of sufficient size, it would be as Turing
complete as any existing machine (or, for those who interpret that excessively
critically, i.e. "not at all" for both, we can simply say that the AE could
simulate any existing machine--although not quickly).  This would be a good
place to site some references on the AE, but I don't have any.


### Definition of the input language to buzzard.1 (OR What Exactly Do All The Macros Do?)

[Don't read this unless you're stumped!]

```
    MACRO     FUNCTION        MNEMONIC

    V         begin variable
              declarations    Variable

    C         begin program   Code

    Q(b,a)    let b = a       eQuals
    A(c,a,b)  let c = a + b   Add
    S(c,a,b)  let c = a - b   Subtract

    D(c,a,b)  let c = a / b,
              where b is a    Divide
              constant

    U(c,a,b)  let c = a / b,
              where b is      Unknown
              anything

    M(c,a,b)  let c = a * b   Multiply

    O(c,a,b)  let c = a       Or
              boolean-or
              b (a,b are
              0 or 1)

    B(b, a)   let             Boolean
              b = boolean
              value of a

    P(b, a)   let b = 1 if
              a>0, else 0.    Positive

    l         emit next
              sequential      Label
              label

    J(x)      goto label #x   Jump

    Z(a,d)    if a is 0
              goto d (a is    Zero
              0 or 1)

    E(a,d)    if a is 1
              goto d          Else
              (a is 0 or 1)

    H         halt            Halt

    K(x)      let x = number
              of cmdline      Kount
              arguments

    G(x,y)    let x = the
              value
              of the yth      Get arg
              argument

    T         end of code;
              begin output    Terminate
              section

    X(y)      print hex
              value of y      heX

    T         end of output   Terminate
              section
              and program
```

You can figure out the other macros yourself.  In the sample program, I've
actually implemented subroutines by saving a return address in a variable and
then jumping to a routine-- specifically, a routine that converts a number into
BCD, so it can be output by the hexadecimal output statement.


### How it works, i.e., how to get useful programs from a op= b

The essential statement to be able to make interesting
programs is the conditional (given that we have loops).
Since all you can do in the given operation output set is
assignment, we implement "conditional assignment":

``` <!---c-->
    if (x) y = z;
```

To implement this, we constrain `x` to be either 0 or 1, and
simply compute:

``` <!---c-->
    y = (z * x) + (y * (1-x));
```

This is more obscured by factoring out common terms and restricting
ourselves to two operand operations:

``` <!---c-->
    temp = z;       (temp == z)
    temp -= y;      (temp == z-y)
    temp *= x;      (temp == (z-y)*x)
    y += temp;      (y    == (z-y)*x + y)
                    (     == z*x - y*x + y)
                    (     == z*x + y*(1-x))
```

Next we imagine we have a [pc](https://en.wikipedia.org/wiki/Program_counter).
"I'm supposed to execute statement pc next", says our emulator.  But suppose
we're not currently coming up on statement pc.  To handle this, we simply make
every operation conditional on the pc having the correct value:

``` <!---c-->
    if (pc == some_constant) y = z;
```

To combine this with other operations, we simply multiply by our
(`pc == some_constant`) flag right after the above `temp *= x`.

To evaluate `pc == some_constant` requires one more trick.  We assume that
numbers can only be in some limited range.  Then we use successive additions and
divisions to reduce that number down to `-1`, `0`, or `1`.  You could, for
instance, do this by using mod by `2` and div by `2` to count bits, stopping
after, say, `32` iterations.  The number you get is between `0..32`, so another
`6` iterations on it reduces it to `0..6`.  Three iterations on this produces
`0..2` (`3` would be `7`), and then two iterations on this produces 0 or 1.
Instead I use a shorter two-divide approach that assumes I'm allowed to use
numbers slightly larger than the numbers I'm operating on.

A similar approach is used to detect positive numbers.

Note that the obvious code to compute `y/x` will not work correctly,
because every value is computed, even if the pc is not set correctly;
if `x` is ever `0` when the real C code reaches this computation the
program will die.  (This was discovered the hard way.)  The solution
is to stick `x` in a temporary, and if the current code is not about
to be executed, set the temporary to `1`.

Thanks to Bill Pugh for bringing the loop-ability of the AE to
my attention.

`buzzard.1` was originally named `cb`, for obvious reasons, and is
dedicated to the memory of Charles Barrett.


<!--

    Copyright © 1984-2024 by Landon Curt Noll. All Rights Reserved.

    You are free to share and adapt this file under the terms of this license:

        Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)

    For more information, see:

        https://creativecommons.org/licenses/by-sa/4.0/

-->