💾 Archived View for bbs.geminispace.org › u › undefined › file › 355 › main.c captured on 2024-12-17 at 15:09:09.

View Raw

More Information

-=-=-=-=-=-=-

/* to compile: cc main.c -o main
 * to run: ./main -f program_name
 * or
 * echo "main text" | ./main
 *
 * SYNTAX:
 * - a single stack of 32-bit signed integers
 * - reverse polish notation
 * - the output is the top of the stack, clamped to a byte and mapped to
 *   printable ascii if possible
 * - spaces between numbers, identifiers and punctuation are not required
 * - function names can only consist of small latin letters and _
 * - numbers are specified in decimal, unless they start with #, in which case they are hex
 * - define subroutines and constants using $
 * - the backslash treats next character as a number, pushing it on the stack
 * - () for comments, nesting is supported
 * - the only data type is a 32-bit signed integer
 * - popping an argument from an empty stack produces 0
 * - no loops, but recursion is supported
 * - if ... else ... end conditional. Does not nest, use procedures if you want nested ifs.
 * - else is optional
 * - poke can change the contents below the top item
 * - peek/poke indexing is always clamped to a reasonable value
 * - details below
 *
 * EXAMPLE PROGRAMS:
 *
 * ( 1. a diagonal tiling )
 * ( push literal values onto the array, then use the calculation as an index into it )
 * \/\\ y 1 band x 1 band xor peek
 *
 * ( 2. a gradient circle )
 *
 * $dup  {peek 0}
 * $sq   {dup mul}
 * $norm {wid 2 div sub sq}
 * \ \. \:\o\@ x norm y norm add 16 div peek
 *
 * ( 3. a seascape )
 * ( here's an example of using multiplication as an alternative to branching, )
 * ( and using addition as layering )
 *
 * $neg{0 1 sub mul} (a -> -a)
 * $hh{hei 2 div} ( -> a)
 * $hw{wid 2 div} ( -> a)
 * $circle_sdf {
 *    y add norm 
 *    swp 
 *    x add norm 
 *    add swp sq div} (radius x_offset y_offset -> dist)
 *
 * \-\:\~\  
 * x 1000 add y 3 add mod 0 eq y hw lt mul y hw eq add ( the waves )
 * 3 4 2 neg circle_sdf ( the sun )
 * 2 lt 2 mu            ( shift the layer )
 * y hw ge mul          ( and only draw above water )
 * add
 * peek
 *
 * ( 4. power function implemented via recursion )
   $pow_ {     (base mul power -> base mul' power-1)
   dup         (base mul pow pow)
   0 gt if     (base mul pow)
       dec     (base mul pow-1)
       swp     (base pow-1 mul)
       2 peek  (base pow-1 mul base)
       mul     (base pow-1 mul')
       swp     (base mul' pow-1)
       pow_
   end
   }
   $pow { ( base power -> base^power)
   1 swp pow_
   pop swp pop
   } (base power -> base^power)
   
   2 10 pow
 *
 * */

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

#define BUILD_DEBUG 1
#define BOARD_WIDTH 40
#define MAX_PROGRAM_SIZE 4096
#define STACK_SIZE 256
#define MAX_RECURSIVE_CALLS 256

typedef uint32_t u32;
typedef int32_t i32;
typedef int32_t b32;

#define false 0
#define true 1

#if BUILD_DEBUG
#define BreakHere do { asm ("int $3"); int __attribute__((unused)) a = 0; int __attribute__((unused)) b = 0; int __attribute__((unused)) c = 0;} while(0);
#else
#include <assert.h>
#define BreakHere do { assert(0); } while(0);
#endif

#define InvalidDefaultCase default: { BreakHere; } break;
#define Assert(Cond) do { if(!(Cond)) { BreakHere; } } while(0);

typedef enum
{
    PARSING_ANY,
    PARSING_DECIMAL,
    PARSING_HEX,
    PARSING_IDENTIFIER,
    PARSING_COMMENT
} parser_state;

typedef struct
{
    u32 Count;
    char *Start;
} string_slice;

#define WITH_BUILTIN(X) \
    X(add) /* (a b -> a+b) */ \
    X(sub) /* (a b -> a-b) */ \
    X(mul) /* (a b -> a*b) */ \
    X(div) /* (a b -> a/b) */ \
    X(mod) /* (a b -> a%b) */ \
    X(or) /* (a b -> a||b) */ \
    X(xor) /* (a b -> a^b) */ \
    X(and) /* (a b -> a&&b) */ \
    X(not) /* (a -> !a) */ \
    X(bor) /* (a b -> a|b) */ \
    X(swp) /* (a b -> b a) */ \
    X(band) /* (a b -> a&b) */ \
    X(bnot) /* (a -> ~a) */ \
    X(eq) /* (a b -> a==b) */ \
    X(neq) /* (a b -> a!=b) */ \
    X(lt) /* (a b -> a<b) */ \
    X(gt) /* (a b -> a>b) */ \
    X(le) /* (a b -> a<=b) */ \
    X(ge) /* (a b -> a>=b) */ \
    X(if) /* (a -> ) if nonzero, skips the else branch, otherwise skips the if branch. does not nest */ \
    X(else) /* optional */ \
    X(end) /* ends the if conditional */ \
    X(shr) /* (a b -> a >> b) */ \
    X(shl) /* (a b -> a << b) */\
    X(pop) /* (a b -> a) */\
    X(peek) /* (a ... a_offset -> a) */ \
    X(poke) /* (a ... a_offset b -> b ...)*/ \
    X(x) /* this cell's x coordinate */ \
    X(y) /* this cell's y coordinate */ \
    X(wid) /* x dimension of the board */ \
    X(hei) /* y dimension of the board */

#define BUILTIN_ENUM(Name) RT_##Name,

typedef enum
{
    RT_Custom,
    WITH_BUILTIN(BUILTIN_ENUM)
    RT_Unknown,
    RT_MaximumPlus1
} routine_type;

#define BUILTIN_IDENTIFIER(Name) [RT_##Name] = {.Count = sizeof(#Name) - 1, .Start = #Name},
static string_slice BuiltinIdentifiers[] =
{
    WITH_BUILTIN(BUILTIN_IDENTIFIER)
};

typedef struct
{
    routine_type Type;
    string_slice Identifier;
    string_slice Text;
} routine;

typedef struct
{
    u32 Allocated;
    u32 Count;
    routine *Routines;
} routine_table;

typedef struct
{
    parser_state State;
    parser_state StateBeforeComment;

    // debugging info
    char C;
    u32 Chari;
    u32 LineCount;

    i32 Number;
    u32 CommentCount;
    string_slice Identifier;
    routine_table *RoutineTable;
    routine CurrentRoutine;
    b32 InsideFunctionName;
    b32 InsideFunctionDefinition;
    b32 NextCharacterIsLiteral;

    u32 RecursionLevel;

    // evaluation data
    b32 Skip;
    i32 *Stack;
    u32 StackTop;

    u32 X, Y;
} parser;

#define UsageAndExit(ExitCode) do { \
fprintf(stderr, \
        "USAGE:" \
        "%s [-f FILENAME]\n", \
        Argv[0]); exit(ExitCode); \
} while(0);

#define ParseError(...) do { \
    fprintf(stderr, "Error at character '%c' (position %d, line %d): ", Parser->C, Parser->Chari, Parser->LineCount); \
    fprintf(stderr, __VA_ARGS__); \
    fprintf(stderr, "\n"); \
    exit(1); \
} while(0);

static routine
RoutineMatch(routine_table *Table, string_slice Identifier)
{
    for(u32 Routinei = 0; Routinei < Table->Count; ++Routinei)
    {
        routine Rt = Table->Routines[Routinei];
        if(Rt.Identifier.Count == Identifier.Count)
        {
            b32 Found = true;
            for(u32 Chari = 0; Chari < Identifier.Count; ++Chari)
            {
                if(Identifier.Start[Chari] != Rt.Identifier.Start[Chari])
                {
                    Found = false;
                    break;
                }
            }
            if(Found)
            {
                return Rt;
            }
        }
    }
    return (routine){.Type = RT_Unknown};
}

static i32
StackPop(parser *Parser)
{
    i32 Top = 0;
    if(Parser->StackTop)
    {
        Top = Parser->Stack[--Parser->StackTop];
    }
    return Top;
}

// quietly fails if stack was going to overflow
static void
StackPush(parser *Parser, i32 Value)
{
    if(Parser->StackTop < STACK_SIZE)
    {
        Parser->Stack[Parser->StackTop++] = Value;
    }
}

static void ParserDoPass(parser *Parser, u32 InputSize, char *Input);

static void
Flush(parser *Parser, parser_state NewState)
{
    Assert(Parser->CommentCount == 0);
    switch(Parser->State)
    {
        case PARSING_ANY:
        { /* do nothing */ } break;
        case PARSING_DECIMAL: // fallthrough
        case PARSING_HEX:
        {
            if(!(Parser->InsideFunctionDefinition || Parser->InsideFunctionName || Parser->Skip))
            {
                StackPush(Parser, Parser->Number);
            }
        } break;
        case PARSING_IDENTIFIER:
        {
            if(!(Parser->InsideFunctionDefinition || Parser->InsideFunctionName))
            {
                routine Routine = RoutineMatch(Parser->RoutineTable, Parser->Identifier);
                if(Parser->Skip)
                {
                    if(Routine.Type == RT_else || Routine.Type == RT_end)
                    {
                        Parser->Skip = false;
                    }
                }
                else
                {
                    switch(Routine.Type)
                    {
                        case RT_Custom:
                        {
                            if(Parser->RecursionLevel < MAX_RECURSIVE_CALLS)
                            {
                                parser Inner =
                                {
                                    .State = PARSING_ANY,
                                    .StateBeforeComment = PARSING_ANY,
                                    .C = 0,
                                    .Chari = 0,
                                    .LineCount = Parser->LineCount,
                                    .Number = 0,
                                    .CommentCount = 0,
                                    .Identifier = {0},
                                    .RoutineTable = Parser->RoutineTable,
                                    .CurrentRoutine = {0},
                                    .InsideFunctionDefinition = false,
                                    .InsideFunctionName = false,
                                    .NextCharacterIsLiteral = false,
                                    .RecursionLevel = Parser->RecursionLevel + 1,
                                    .Stack = Parser->Stack,
                                    .StackTop = Parser->StackTop,
                                    .X = Parser->X,
                                    .Y = Parser->Y
                                };
                                ParserDoPass(&Inner, Routine.Text.Count, Routine.Text.Start);
                                Parser->StackTop = Inner.StackTop;
                            }
                        } break;

#define BUILTIN_TWO(Name, Payload) \
                        case Name: \
                                   { \
                                       i32 B = StackPop(Parser); \
                                       i32 A = StackPop(Parser); \
                                       StackPush(Parser, Payload); \
                                   } break;

                        BUILTIN_TWO(RT_add, A+B);
                        BUILTIN_TWO(RT_mul, A*B);
                        BUILTIN_TWO(RT_sub, A-B);
                        BUILTIN_TWO(RT_div, (B ? A/B : 0));
                        BUILTIN_TWO(RT_mod, (B ? A%B : 0));
                        BUILTIN_TWO(RT_or, A || B);
                        BUILTIN_TWO(RT_and, A && B);
                        BUILTIN_TWO(RT_band, A & B);
                        BUILTIN_TWO(RT_bor, A | B);
                        BUILTIN_TWO(RT_xor, A ^ B);
                        BUILTIN_TWO(RT_shr, A >> B);
                        BUILTIN_TWO(RT_shl, A << B);
                        BUILTIN_TWO(RT_eq, A == B);
                        BUILTIN_TWO(RT_neq, A != B);
                        BUILTIN_TWO(RT_gt, A > B);
                        BUILTIN_TWO(RT_lt, A < B);
                        BUILTIN_TWO(RT_ge, A >= B);
                        BUILTIN_TWO(RT_le, A <= B);
                        case RT_not:
                        {
                            i32 A = StackPop(Parser);
                            StackPush(Parser, !A);
                        } break;
                        case RT_bnot:
                        {
                            i32 A = StackPop(Parser);
                            StackPush(Parser, ~A);
                        } break;
                        case RT_swp:
                        {
                            i32 B = StackPop(Parser);
                            i32 A = StackPop(Parser);
                            StackPush(Parser, B);
                            StackPush(Parser, A);
                        } break;
                        case RT_if:
                        {
                            i32 Test = StackPop(Parser);
                            if(Test == 0) { Parser->Skip = true; }
                        } break;
                        case RT_else:
                        {
                            Parser->Skip = true;
                        } break;
                        case RT_end:
                        {
                            Parser->Skip = false;
                        } break;
                        case RT_x:
                        {
                            StackPush(Parser, (i32)Parser->X);
                        } break;
                        case RT_y:
                        {
                            StackPush(Parser, (i32)Parser->Y);
                        } break;
                        case RT_wid: // fallthrough
                        case RT_hei:
                        {
                            StackPush(Parser, (i32)BOARD_WIDTH);
                        } break;
                        case RT_pop:
                        {
                            StackPop(Parser);
                        } break;
                        case RT_peek:
                        {
                            i32 Offset = StackPop(Parser);
                            if(Parser->StackTop)
                            {
                                i32 TopOffset = (i32)(Parser->StackTop)-1;
                                if(Offset > TopOffset) { Offset = TopOffset; } 
                                if(Offset < 0) { Offset = 0; }

                                StackPush(Parser, Parser->Stack[TopOffset-Offset]);
                            }
                            else
                            {
                                StackPush(Parser, 0);
                            }
                        } break;
                        case RT_poke:
                        {
                            i32 Value = StackPop(Parser);
                            i32 Offset = StackPop(Parser);
                            if(Parser->StackTop)
                            {
                                i32 TopOffset = (i32)(Parser->StackTop)-1;
                                if(Offset > TopOffset) { Offset = TopOffset; } 
                                if(Offset < 0) { Offset = 0; }

                                Parser->Stack[TopOffset-Offset] = Value;
                            }
                        } break;
                        case RT_Unknown:
                        {
                            ParseError("unrecognized routine: %.*s\n", Parser->Identifier.Count, Parser->Identifier.Start);
                        } break;
                        InvalidDefaultCase;
                    }
                }
            }
            else if(Parser->InsideFunctionName)
            {
                Parser->CurrentRoutine.Identifier = Parser->Identifier;
            }
        } break;
        InvalidDefaultCase;
    }
    Parser->Number = 0;
    Parser->Identifier = (string_slice){0};
    Parser->State = NewState;
}

static void
AddRoutine(parser *Parser, routine_type Type, string_slice Identifier, string_slice Text)
{
    routine_table *Table = Parser->RoutineTable;
    routine Check = RoutineMatch(Table, Identifier);
    if(Check.Type != RT_Unknown)
    {
        ParseError("a routine with the name '%.*s' already exists", Identifier.Count, Identifier.Start);
    }
    routine Routine = 
    {
        .Type = Type,
        .Identifier = Identifier,
        .Text = Text
    };
    if(Type > RT_Custom)
    {
        Assert(Type < RT_MaximumPlus1);
        Assert(Text.Count == 0);
        Assert(Text.Start == 0);
    }
    else
    {
        Assert(Text.Start);
        if(!Text.Count)
        {
            ParseError("an empty subroutine body for %.*s", Identifier.Count, Identifier.Start);
        }
    }
    if(Table->Count + 1 > Table->Allocated)
    {
        Table->Allocated *= 2;
        Table->Routines = realloc(Table->Routines, Table->Allocated*sizeof(routine));
    }
    Table->Routines[Table->Count++] = Routine;
}

static void
ParserDoPass(parser *Parser, u32 InputSize, char *Input)
{
    for(u32 Chari = 0; Chari < InputSize; ++Chari)
    {
        char C = Input[Chari];
        Parser->C = C;
        Parser->Chari = Chari;
        if(Parser->NextCharacterIsLiteral)
        {
            Parser->NextCharacterIsLiteral = false;
            Parser->Number = C;
            Flush(Parser, PARSING_ANY);
        }
        else if(Parser->State == PARSING_COMMENT)
        {
            if(C == ')')
            {
                --Parser->CommentCount;
                if(Parser->CommentCount == 0)
                {
                    Parser->State = Parser->StateBeforeComment;
                }
            }
            else if(C == '(')
            {
                ++Parser->CommentCount;
            }
        }
        else if(Parser->InsideFunctionName)
        {
            if(C == '{')
            {
                if(Chari + 1 == InputSize)
                {
                    ParseError("empty function body");
                }
                Flush(Parser, PARSING_ANY);
                Parser->InsideFunctionName = 0;
                Parser->InsideFunctionDefinition = 1;
                Assert(Parser->CurrentRoutine.Identifier.Count);
                Assert(Parser->CurrentRoutine.Identifier.Start);
                Parser->CurrentRoutine.Text.Start = Input + Chari + 1;
                Assert(Parser->CurrentRoutine.Text.Count == 0);
            }
            else if((C >= 'a' && C <= 'z') || (C == '_'))
            {
                if(Parser->State != PARSING_IDENTIFIER)
                {
                    Flush(Parser, PARSING_IDENTIFIER);
                }
                if(!Parser->Identifier.Start)
                {
                    Parser->Identifier.Start = Input + Chari;
                }
                ++Parser->Identifier.Count;
            }
            else if(C == '\n' || C == '\r' || C == '\n' || C == '\t' || C == ' ')
            {
                if(C == '\n') { ++Parser->LineCount; }
                Flush(Parser, PARSING_ANY);
            }
            else
            {
                ParseError("a routine body must follow the routine definition");
            }
        }
        else
        {
            switch(C)
            {
                case '0': // fallthrough
                case '1': // fallthrough
                case '2': // fallthrough
                case '3': // fallthrough
                case '4': // fallthrough
                case '5': // fallthrough
                case '6': // fallthrough
                case '7': // fallthrough
                case '8': // fallthrough
                case '9':
                {
                    if(Parser->State == PARSING_HEX)
                    {
                        Parser->Number *= 16;
                        Parser->Number += C - '0';
                    }
                    else
                    {
                        if(Parser->State != PARSING_DECIMAL)
                        {
                            Flush(Parser, PARSING_DECIMAL);
                        }
                        Parser->Number *= 10;
                        Parser->Number += C - '0';
                    }
                } break;
                case '#':
                {
                    Flush(Parser, PARSING_HEX);
                } break;
                case '


:
                {
                    Flush(Parser, PARSING_IDENTIFIER);
                    Parser->InsideFunctionName = 1;
                } break;
                case '(':
                {
                    if(Parser->CommentCount == 0)
                    {
                        Parser->StateBeforeComment = Parser->State;
                        Flush(Parser, PARSING_COMMENT);
                    }
                    ++Parser->CommentCount;
                } break;
                case ')':
                {
                    ParseError("unexpected comment closing brace");
                } break;
                case '{':
                {
                    ParseError("unexpected opening brace");
                } break;
                case '}':
                {
                    if(!Parser->InsideFunctionDefinition)
                    {
                        ParseError("unexpected closing brace");
                    }
                    Parser->CurrentRoutine.Text.Count = (u32)((Input + Chari) - Parser->CurrentRoutine.Text.Start);
                    if((Parser->X == 0) && (Parser->Y == BOARD_WIDTH-1))
                    {
                        AddRoutine(Parser, RT_Custom, Parser->CurrentRoutine.Identifier, Parser->CurrentRoutine.Text);
                    }
                    Flush(Parser, PARSING_ANY);
                    Parser->CurrentRoutine = (routine){0};
                    Parser->InsideFunctionDefinition = 0;
                } break;
                case 'A': // fallthrough
                case 'B': // fallthrough
                case 'C': // fallthrough
                case 'D': // fallthrough
                case 'E': // fallthrough
                case 'F':
                {
                    if(Parser->State != PARSING_HEX)
                    {
                        ParseError("A-F can only be used in a hex number");
                    }
                    Parser->Number *= 16;
                    Parser->Number += C - 'A' + 10;
                } break;
                case 'a': // fallthrough
                case 'b': // fallthrough
                case 'c': // fallthrough
                case 'd': // fallthrough
                case 'e': // fallthrough
                case 'f': // fallthrough
                case 'g': // fallthrough
                case 'h': // fallthrough
                case 'i': // fallthrough
                case 'j': // fallthrough
                case 'k': // fallthrough
                case 'l': // fallthrough
                case 'm': // fallthrough
                case 'n': // fallthrough
                case 'o': // fallthrough
                case 'p': // fallthrough
                case 'q': // fallthrough
                case 'r': // fallthrough
                case 's': // fallthrough
                case 't': // fallthrough
                case 'u': // fallthrough
                case 'v': // fallthrough
                case 'w': // fallthrough
                case 'x': // fallthrough
                case 'y': // fallthrough
                case 'z': // fallthrough
                case '_':
                {
                    if(Parser->State != PARSING_IDENTIFIER)
                    {
                        Flush(Parser, PARSING_IDENTIFIER);
                    }
                    if(!Parser->Identifier.Start)
                    {
                        Parser->Identifier.Start = Input + Chari;
                    }
                    ++Parser->Identifier.Count;
                } break;
                case '\\':
                {
                    Flush(Parser, PARSING_DECIMAL);
                    Parser->NextCharacterIsLiteral = 1;
                } break;
                case '\n':
                    ++Parser->LineCount; // fallthrough
                case '\r': // fallthrough
                case '\t': // fallthrough
                case ' ':
                {
                    Flush(Parser, PARSING_ANY);
                } break;
                default:
                {
                    ParseError("unexpected character");
                } break;
            }
        }
    }
    Flush(Parser,PARSING_ANY);
}

int main(int Argc, char **Argv)
{
    FILE *InputFile = stdin;
    for(int Argi = 1; Argi < Argc; ++Argi)
    {
        char *Arg = Argv[Argi];
        if(Arg[0] == '-' && Arg[1] == 'f' && Arg[2] == 0)
        {
            if(Argi + 1 < Argc)
            {
                InputFile = fopen(Argv[Argi+1], "rb");
                if(!InputFile)
                {
                    UsageAndExit(1);
                }
                ++Argi;
            }
            else
            {
                UsageAndExit(1);
            }
        }
    }
    char *Input = malloc(MAX_PROGRAM_SIZE);
    u32 InputSize = fread(Input, 1, MAX_PROGRAM_SIZE, InputFile);
    if(InputSize == 0 || InputSize == MAX_PROGRAM_SIZE)
    {
        UsageAndExit(1);
    }

    u32 RoutinesToAllocate = (u32)RT_MaximumPlus1 + 32;
    routine_table RoutineTable = 
    {
        .Allocated = RoutinesToAllocate,
        .Count = 0,
        .Routines = (routine *)malloc(sizeof(routine)*RoutinesToAllocate)
    };
    parser Parser =
    {
        .State = PARSING_ANY,
        .StateBeforeComment = PARSING_ANY,
        .Number = 0,
        .CommentCount = 0,
        .Identifier = {.Start = 0, .Count = 0},
        .RoutineTable = &RoutineTable,
        .CurrentRoutine = {0},
        .InsideFunctionDefinition = false,
        .NextCharacterIsLiteral = false,
    };

    // create the builtins
    string_slice EmptyText = {.Count = 0, .Start = 0};
    for(u32 Builtini = (u32)RT_Custom + 1;
        Builtini < RT_MaximumPlus1;
        ++Builtini)
    {
        AddRoutine(&Parser, (routine_type)Builtini, BuiltinIdentifiers[Builtini], EmptyText);
    }

    i32 *Stack = calloc(1, sizeof(i32)*STACK_SIZE);
    for(u32 Y = BOARD_WIDTH-1; ; --Y)
    {
        for(u32 X = 0; X < BOARD_WIDTH; ++X)
        {
            Parser = (parser)
            {
                .State = PARSING_ANY,
                .StateBeforeComment = PARSING_ANY,
                .Number = 0,
                .CommentCount = 0,
                .Identifier = {0},
                .CurrentRoutine = {0},
                .InsideFunctionName = false,
                .InsideFunctionDefinition = false,
                .Stack = Stack,
                .StackTop = 0,
                .RoutineTable = &RoutineTable,
                .RecursionLevel = 0,
                .Skip = false,
                .X = X,
                .Y = Y
            };
            ParserDoPass(&Parser, InputSize, Input);
            i32 Result = Parser.StackTop ? Parser.Stack[Parser.StackTop-1] : 0;
            if(Result >= ' ' && Result <= '~')
            {
                printf("%c", Result);
            }
            else
            {
                printf("[%d]", Result);
            }
        }
        printf("\n");
        if(Y == 0) { break; }
    }
}