seriot.ch

About | Projects | Trail

PostScript Tiny Ray Tracer

March 2025

A Tiny Ray Tracer in PostScript

Takashi Hayakawa won the 1st prize of the Obfuscated PostScript Contest 1993 with a stunning, tiny ray tracer.

Let's analyze the obfuscation techniques he used, and see how we can minimize the code further. Note that we won't analyze the ray tracing algorithm per se, but focus on the code minimization techniques instead.

Source Code
Understand the minimization techniques
Further improvements
Results and conclusion
Bonus: a failed attempt: lookup table for parsing

1. Source Code

The program comes in two versions:

Version 1: Tiny_RayTracing.ps (760 bytes without newlines)

%!OPS-1.0 %%Creator: HAYAKAWA,Takashi
/A/copy/p/floor/q/gt/S/add/n/exch/i/index/J/ifelse/r/roll/w/div/H{{loop}stopped
Y}def/t/and/C/neg/T/dup/h/exp/Y/pop/d/mul/s/cvi/e/sqrt/R/rlineto{load def}H 300
T translate(V2L&1i2A00053r45hNvQXz&vUX&UOvQXzFJ!FJ!J!O&Y43d9rE3IaN96r63rvx2dcaN
G&140N7!U&4C577d7!z&&93r6IQO2Z4o3AQYaNlxS2w!!f&nY9wn7wpSps1t1S!D&cjS5o32rS4oS3o
Z&blxC1SdC9n5dh!I&3STinTinTinY!B&V0R0VRVC0R!N&3A3Axe1nwc!l&993dC99Cc96raN!a&1CD
E&YYY!F&&vGYx4oGbxSd0nq&3IGbxSGY4Ixwca3AlvvUkbQkdbGYx4ofwnw!&vlx2w13wSb8Z4wS!J!
c&j1idj2id42rd!X&4I3Ax52r8Ia3A3Ax65rTdCS4iw5o5IxnwTTd32rCST0q&eCST0q&D1!&EYE0!J
&EYEY0!J0q!x&jd5o32rd4odSS!K&WCVW!Q&31C85d4!k&X&E9!&1!J!v&6A!b&7o!o&1r!j&43r!W)
{( )T 0 4 3 r put T(/)q{T(9)q{cvn}{s}J}{($)q{[}{]}J}J cvx}forall 270{def}H
K{K{L setgray moveto B fill}for Y}for showpage

Version 2: Tiny_RayTracing.HINT (809 bytes without newlines)

%! Tiny RayTracing by HAYAKAWA,Takashi
/p/floor/S/add/A/copy/n/exch/i/index/J/ifelse/r/roll/e/sqrt/H{count 2 idiv exch
repeat}def/q/gt/h/exp/t/and/C/neg/T/dup/Y/pop/d/mul/w/div/s/cvi/R/rlineto{load
def}H/c(j1idj2id42rd)/G(140N7)/Q(31C85d4)/B(V0R0VRVC0R)/K(WCVW)/U(4C577d7)300
T translate/I(3STinTinTinY)/l(993dC99Cc96raN)/k(X&E9!&1!J)/Z(blxC1SdC9n5dh)/j
(43r)/O(Y43d9rE3IaN96r63rvx2dcaN)/z(&93r6IQO2Z4o3AQYaNlxS2w!)/N(3A3Axe1nwc)/W
270 def/L(1i2A00053r45hNvQXz&vUX&UOvQXzFJ!FJ!J)/D(cjS5o32rS4oS3o)/v(6A)/b(7o)
/F(&vGYx4oGbxSd0nq&3IGbxSGY4Ixwca3AlvvUkbQkdbGYx4ofwnw!&vlx2w13wSb8Z4wS!J!)/X
(4I3Ax52r8Ia3A3Ax65rTdCS4iw5o5IxnwTTd32rCST0q&eCST0q&D1!&EYE0!J!&EYEY0!J0q)/V
3 def/x(jd5o32rd4odSS)/a(1CD)/E(YYY)/o(1r)/f(nY9wn7wpSps1t1S){[n{( )T 0 4 3 r
put T(/)q{T(9)q{cvn}{s}J}{($)q{[}{]}J}J cvx}forall]cvx def}H K{K{L setgray
moveto B fill}for Y}for showpage

Version 1 is super compact. The author mentions it's 761 bytes, but you can reduce it down to 760 bytes by removing a newline character.

Tiny_RayTracing_760.ps

Version 2 is slightly more verbose (and readable): 809 bytes without newline characters. The rendering quality can be adjusted with the V key: 2 to match original version, 3 to decrease it slightly, etc.

Tiny_RayTracing_hint_809.ps

These PostScript programs can be run with ps2pdf:

ps2pdf Tiny_RayTracing.ps

or directly in GhostView:

gv Tiny_RayTracing.ps

Let's analyze version 2, Tiny_RayTracing_hint_809.ps.

2. Understand the minimization techniques

Let's go through the expanded version Tiny_RayTracing_hint_809_.ps (note the trailing underscore).

The program has three mains parts: 1. Define operator aliases 2. Encode procedures into strings 3. Extract procedures out of encoded strings

2.1 Define operator aliases

First, the program creates one-letter aliases for some operators:

% push pairs of one-letter keys and operators
/p/floor
/S/add
/A/copy
/n/exch
% ...

% associate the keys with the operators
count 2 idiv {  % push stack count / 2    
    load        % load operator
    def         % associate single-letter name with it
} repeat        % repeat for all pairs

2.2 Encode procedures into strings

Second, the program encodes specific procedures into strings, and attach them more one-letter aliases.

/k(X&E9!&1!J)   % will be parsed as an executable procedure

2.3 Extract procedures out of encoded strings

Third, the program parses the strings and builds executable arrays of PostScript tokens out of them, converting each character into either a number, an operator, or a control structure.

{
    [                                 % open array
        exch {
            ( ) dup 0 4 3 roll put    % convert character to string
            dup (/) gt {              
                dup (9) gt {          
                    cvn               % ASCII 58-127 -> a name
                } {                   
                    cvi               % ASCII 48-57  -> a digit (0-9)
                } ifelse              
            } {                       
                ($) gt {              
                    [                 % ASCII 36-47  -> open bracket  (&)
                } {                   %
                    ]                 % ASCII 58-127 -> close bracket (!)
                } ifelse
            } ifelse
            cvx                       % make executable                
        } forall                
    ] cvx def                         % close array and convert into procedure
} count 2 idiv exch repeat            % for all pairs key / procedure

For example, /k(X&E9!&1!J) is converted into:

/k {
    X {
        E 9
    } {
        1
    } ifelse
} def

2.4 Encode your own procedure

Can we encode a procedure of our own? Let's try with this Fibonacci procedure:

/fib {
    dup 1 gt {
        1 sub dup 1 sub fib exch fib add
    } if
} def

Tiny_RayTracing.ps doesn't provide aliases for sub and if operators.

We could add them, but we can also slightly adapt the fib procedure so that it only uses the shortcuts alerady defined:

/fib {
    dup 1 gt {
        1 neg add dup 1 neg add fib exch fib add
    } {
    } ifelse
} def

Encode the Fibonacci procedure by replacing dup with T, { with &, etc.

/_(T1q&1CST1CS_n_S!&!J)

And now you can add this definition before the parser, call it at the end of the program and check that it works: Tiny_RayTracing_hint_fib_.ps.

7 _ == % 13

3. Further improvements

This encoding scheme is pretty neat, but can we improve it to shorten the code further?

3.1 Implicit aliases for operators

Instead of pushing pairs of letters and operator names, we can push the operators only. While unpiling these names, we create one-letter strings based on the stack count (..., d, c, b, a), make the names executable and associate them with the one-letter string.

/ifelse
/neg
/rlineto
/mul
% ...

count {
    ( ) dup 0 count 93 add put
    exch cvx def
} repeat

3.2 Implicit aliases for encoded strings

Ray tracer version 1 pushes keys and encoded strings:

/c(j1idj2id42rd)
/G(140N7)
/Q(31C85d4)

The more compact Ray tracer version 2 pushes one single string, that will be parsed into /key1 proc1, /key2 proc2, ....

For instance, parsing this string:

(V2L&1i2A00053r45hNvQXz&vUX&UOvQXzFJ!FJ!J!)

will leave that on the stack, ready for easy key-value association:

{1 i 2 A 0 0 0 5 3 r 4 5 h N v Q X z {v U X {U O v Q X z F J} F J} J}
L
2
V

In the spirit of our "implicit aliases for operators", we can improve the encoding scheme to make it even shorter:

For instance, parsing this string:

(&X&E9 1!a gin 3j!)

will leave the stack as such, ready for enumeration with count {} repeat, and association with capital letters:

{3 j}
{g i n}
{X {E 9} {1} a}

So, we'll end up with something like:

/C {X {E 9} {1} a} def
/B {g i n} def
/A {3 j} def

Note that we cannot define more than 31 procedures this way, since we only use ASCII characters between 60 (<) and 90 (Z), both included.

3.3 Miscellaneous

I've managed to save some bytes in the encoding string, mainly, by:

replacing &! (ie }{) with a single space to mean the same
extracting repeats into new procedures
inlining some procedures
inlining the 270 define (6 5 9 mul mul -> 659dd)
various other tricks of the same kind

4. Results and conclusion

We've analyzed the minimization techniques used in Hayakawa's raytracer 32 years ago.

We've managed to improve these techniques to shorten Hayakawa's code from 760 bytes down to 727 bytes: 727.ps:

/z{def}def/_{count}z/ifelse/neg/rlineto/mul/sqrt/div/dup/exp/index/copy/and/cvi
/add/exch/pop/floor/gt/roll/sub _{( )dup 0 _ 93 add put exch cvx z}repeat/y{( )g
0 4 3 r put}z(&VQXM GJWm 5P32r GoW4P sg0q 1bD 20c02c2b0c S1idS2id42rd CSm>m4Pm3\
P ooo &V?=d0nq&3I=Go4IWfCAZRVVUTJQTdJ?no9fn7fpmpl1k1mfnf VRW2f13fmJ8H4fm!a! 140\
N7 JRWb1mdb9n5dh 3mYYYo 7P 659ddgbn2n 1i2j00053r45hN<&VUX&UO<Fa!Fa!a &93r6IQO2H\
4PZQoANRWm2f! ZZWe1nfC o43d9rE3IAN96r63rVW2dCAN 1r 31b85d4 993db99bC96rAN 43r X\
&E9 1!a 4b577d7 6j Sd>d4Pdmm 4IZW52r8IAZZW65rgds4if5P5IWnfggd32r@&e@&D1 EoE0!a \
EoEo0!a0q gin 3j!){g 47 q{g 57 q{y cvn}{48 s}a}{g 35 q{o[}{32 q{]}{]cvx[}a}a}a
cvx}forall _{_ 59 m y n z}repeat 300 g translate K{K{L setgray moveto B fill}for
}for showpage

Expanded version: 727_.ps.

5. Bonus: a failed attempt: lookup table for parsing

For the record, here is an alternative solution among the various ones that I tried: lookup_742.ps, expanded version lookup_742_.ps.

It does "only" minimise the code down to 742 characters, but does it in quite an elegant way IMHO.

Instead of parsing the string integers with several ifelse, we build an array of code to execute for each value from 0 to 127.

/* [
    33 {{ pop ] cvx [                    }}$ % incl. space
       {  pop ] cvs                      }   % !
    14 {{ pop [                          }}$ % incl. &
    10 {{ 48 sub                         }}$ % numbers
    78 {{ ( ) dup 0 4 3 roll put cvn def }}$ % names
] def

The whole parsing code is then replaced with:

{ dup * exch get exec def } forall