SAF/examples/comun.h

#ifndef _COMUN_H
#define _COMUN_H

/** Comun programming language implemented as a KISS header only C99 library.
  
  [][][] [][][] [][][] []  [] [][][]
  []     []  [] [][][] []  [] []  []
  [][][] [][][] []  [] [][][] []  []

  The interpreter implemented here is supposed to be small and simple rather
  than fast and efficient.

  By drummyfish, released under CC0 1.0, public domain. */

#include <stdint.h>

#define CMN_LANG_VERSION_STRING "TODO" ///< implemented language version
#define CMN_LIB_VERSION_STRING "0.2d" ///< implementation (not language) version

#define CMN_NATIVE_UINT unsigned int

#ifndef CMN_TOKEN_MAX_LENGTH
/** Maximum allowed token length. */
  #define CMN_TOKEN_MAX_LENGTH 128
#endif

#ifndef CMN_PARSE_STACK_SIZE
/** Size of compile stack, says how many levels of nesting can be processed. */
  #define CMN_PARSE_STACK_SIZE 128
#endif

#ifndef CMN_INTERPRETER_CALLSTACK_SIZE
/** Size of the interpreter call stack, says the max depth of function calls. */
  #define CMN_INTERPRETER_CALLSTACK_SIZE 64 
#endif

#ifndef CMN_STRING_PSEUDOHASH_SIZE
/** Size, in bytes, of string pseudohash that's used in symbol table. This
  should be at least 8. Increasing this lowers the probability of string hash
  collision (should be reasonably low with the default value). */
  #define CMN_STRING_PSEUDOHASH_SIZE 8
#endif

#define CMN_MINIMUM_STACK_SIZE 16 ///< Minimum main stack size by specification.

/** Converts an unsigned value to signed as it would happen in two's complement,
  which is not guaranteed in C, so this function exists for portability. */
int32_t CMN_unsignedToSigned32(uint32_t value, uint8_t bits);

int CMN_unsignedToSignedNative(CMN_NATIVE_UINT value); 

/** Creates a pseudohash from given string and type char (type char specifies
  a group of symbols, e.g. function names, variable names etc.). Pseudohash is
  a fixed width string with low probability of collisions with other
  pseudohashes. Pseudohash will only consist of such characters that it will be
  a valid comun/C identifier, but keep in mind the temrinating 0 won't be
  present. */
void CMN_pseudohash(char typeChar, const char *str,
  char hash[CMN_STRING_PSEUDOHASH_SIZE]);

uint64_t CMN_literalValue(const char *literalString, uint8_t *negative,
  uint8_t *ok);

// tokenizer states:
#define CMN_TOKENIZER_NOTHING  0x00
#define CMN_TOKENIZER_TOKEN    0x01
#define CMN_TOKENIZER_ERROR    0x02
#define _CMN_TOKENIZER_BLANK   0x03
#define _CMN_TOKENIZER_COMMENT 0x04
#define _CMN_TOKENIZER_STR     0x05
#define _CMN_TOKENIZER_STR_END 0x06
#define _CMN_TOKENIZER_NAME    0x07

// possible types of tokens returned by tokenizer:
#define CMN_TOKEN_ERROR        0x00
#define CMN_TOKEN_COMMAND      0x01
#define CMN_TOKEN_NAME         0x02
#define CMN_TOKEN_FUNC         0x03
#define CMN_TOKEN_NUMBER       0x04
#define CMN_TOKEN_STRING       0x05
#define CMN_TOKEN_BRANCH       0x06
#define CMN_TOKEN_LOOP         0x07
#define CMN_TOKEN_END          0x08
#define CMN_TOKEN_ELSE         0x09
#define CMN_TOKEN_BREAK        0x0a
#define CMN_TOKEN_LABEL        0x0b

/** Serves to convert a stream of source code characters to a stream of language
  tokens. */
typedef struct
{
  uint8_t state;
  char tokenString[CMN_TOKEN_MAX_LENGTH + 1];
  uint16_t tokenStringPos;
} CMN_Tokenizer;

void CMN_tokenizerInit(CMN_Tokenizer *tokenizer);
uint8_t CMN_tokenizerFeedChar(CMN_Tokenizer *tokenizer, char character); 
uint8_t CMN_identifyToken(const char *tokenString);

#define CMN_BYTECODE_HEADER_SIZE 8
#define CMN_BYTECODE_CHECKSUM_BYTE 4

/// instruction parameters
#define CMN_IPARAMS(typeEnv,noPop,constCont,immediateC)\
  (((typeEnv) << 6) | ((noPop) << 5) | ((constCont) << 4) | (immediateC))

// values for the DES instruction:
#define CMN_DES_IF           0x01
#define CMN_DES_ELSE         0x02
#define CMN_DES_IF_END       0x03
#define CMN_DES_LOOP         0x04
#define CMN_DES_LOOP_BREAK   0x05
#define CMN_DES_LOOP_END     0x06
#define CMN_DES_FUNC         0x07
#define CMN_DES_EXIT         0x08
#define CMN_DES_GOTO         0x09
#define CMN_DES_LABEL        0x0a

#define CMN_MASK_INSTR_NOPOP 0x20 ///< "no pop" bit
#define CMN_MASK_INSTR_CON   0x10 ///< "constant continue" bit
#define CMN_MASK_INSTR_MODE  0x03 ///< mode of typical instructions
#define CMN_MASK_INSTR_GROUP 0xfc

#define CMN_OPCODE_SPECIALS  0x1f ///< upper bound of special instructions

#define CMN_LAST_SPECIAL_PTR 15   ///< last special pointer index

// instruction modes:
#define CMN_OPCODE_21  0 ///< mode: pop 2, push 1
#define CMN_OPCODE_1C1 1 ///< mode: pop 1, use immediate const., push 1
#define CMN_OPCODE_11  2 ///< mode: pop 1, push 1
#define CMN_OPCODE_01  3 ///< mode: push 1

// instruction groups:
#define CMN_OPCODE_AD 0x20
#define CMN_OPCODE_SU 0x24
#define CMN_OPCODE_MU 0x28
#define CMN_OPCODE_DI 0x2c
#define CMN_OPCODE_DS 0x30
#define CMN_OPCODE_MO 0x34
#define CMN_OPCODE_MS 0x38

#define CMN_OPCODE_GR 0x40
#define CMN_OPCODE_GE 0x44
#define CMN_OPCODE_SM 0x48
#define CMN_OPCODE_SE 0x4c

#define CMN_OPCODE_GS 0x50
#define CMN_OPCODE_BS 0x54
#define CMN_OPCODE_SS 0x58
#define CMN_OPCODE_LS 0x5c

#define CMN_OPCODE_EQ 0x60
#define CMN_OPCODE_NE 0x64

#define CMN_OPCODE_BA 0x68
#define CMN_OPCODE_BO 0x6c
#define CMN_OPCODE_BX 0x70
#define CMN_OPCODE_LA 0x74
#define CMN_OPCODE_LO 0x78
#define CMN_OPCODE_LX 0x7c

// SPECIFIC OPCODES:

// special instructions:
#define CMN_OPCODE_END 0x00
#define CMN_OPCODE_NOP 0x01
#define CMN_OPCODE_DES 0x02
#define CMN_OPCODE_COC 0x03
#define CMN_OPCODE_ERR 0x04

#define CMN_OPCODE_CAL 0x07
#define CMN_OPCODE_CAE 0x08
#define CMN_OPCODE_RET 0x09

#define CMN_OPCODE_JIA 0x0a
#define CMN_OPCODE_JNA 0x0b
#define CMN_OPCODE_JMA 0x0c

#define CMN_OPCODE_INI 0x0f

#define CMN_OPCODE_PSC 0x10
#define CMN_OPCODE_PAC 0x11
#define CMN_OPCODE_PAX 0x12
#define CMN_OPCODE_PCO 0x13
#define CMN_OPCODE_MEX 0x14
#define CMN_OPCODE_MGE 0x15
#define CMN_OPCODE_PUX 0x16
#define CMN_OPCODE_PCM 0x17

#define CMN_OPCODE_CON 0x1a
#define CMN_OPCODE_CND 0x1b
#define CMN_OPCODE_SWP 0x1c
#define CMN_OPCODE_TRA 0x1d
#define CMN_OPCODE_POP 0x1e
#define CMN_OPCODE_OUT 0x1f    

// typical stack instructions, fit one of the predefined modes:
#define CMN_OPCODE_ADX (CMN_OPCODE_AD | CMN_OPCODE_21)
#define CMN_OPCODE_ADC (CMN_OPCODE_AD | CMN_OPCODE_1C1)
#define CMN_OPCODE_SUX (CMN_OPCODE_SU | CMN_OPCODE_21)
#define CMN_OPCODE_SUC (CMN_OPCODE_SU | CMN_OPCODE_1C1)
#define CMN_OPCODE_MUX (CMN_OPCODE_MU | CMN_OPCODE_21)
#define CMN_OPCODE_MUC (CMN_OPCODE_MU | CMN_OPCODE_1C1)
#define CMN_OPCODE_DIX (CMN_OPCODE_DI | CMN_OPCODE_21)
#define CMN_OPCODE_DIC (CMN_OPCODE_DI | CMN_OPCODE_1C1)
#define CMN_OPCODE_DSX (CMN_OPCODE_DS | CMN_OPCODE_21)
#define CMN_OPCODE_DSC (CMN_OPCODE_DS | CMN_OPCODE_1C1)
#define CMN_OPCODE_MOX (CMN_OPCODE_MO | CMN_OPCODE_21)
#define CMN_OPCODE_MOC (CMN_OPCODE_MO | CMN_OPCODE_1C1)
#define CMN_OPCODE_MSX (CMN_OPCODE_MS | CMN_OPCODE_21)
#define CMN_OPCODE_MSC (CMN_OPCODE_MS | CMN_OPCODE_1C1)

#define CMN_OPCODE_GRX (CMN_OPCODE_GR | CMN_OPCODE_21)
#define CMN_OPCODE_GRC (CMN_OPCODE_GR | CMN_OPCODE_1C1)
#define CMN_OPCODE_GEX (CMN_OPCODE_GE | CMN_OPCODE_21)
#define CMN_OPCODE_GEC (CMN_OPCODE_GE | CMN_OPCODE_1C1)
#define CMN_OPCODE_SMX (CMN_OPCODE_SM | CMN_OPCODE_21)
#define CMN_OPCODE_SMC (CMN_OPCODE_SM | CMN_OPCODE_1C1)
#define CMN_OPCODE_SEX (CMN_OPCODE_SE | CMN_OPCODE_21)
#define CMN_OPCODE_SEC (CMN_OPCODE_SE | CMN_OPCODE_1C1)

#define CMN_OPCODE_GSX (CMN_OPCODE_GS | CMN_OPCODE_21)
#define CMN_OPCODE_GSC (CMN_OPCODE_GS | CMN_OPCODE_1C1)
#define CMN_OPCODE_BSX (CMN_OPCODE_BS | CMN_OPCODE_21)
#define CMN_OPCODE_BSC (CMN_OPCODE_BS | CMN_OPCODE_1C1)
#define CMN_OPCODE_SSX (CMN_OPCODE_SS | CMN_OPCODE_21)
#define CMN_OPCODE_SSC (CMN_OPCODE_SS | CMN_OPCODE_1C1)
#define CMN_OPCODE_LSX (CMN_OPCODE_LS | CMN_OPCODE_21)
#define CMN_OPCODE_LSC (CMN_OPCODE_LS | CMN_OPCODE_1C1)

#define CMN_OPCODE_EQX (CMN_OPCODE_EQ | CMN_OPCODE_21)
#define CMN_OPCODE_EQC (CMN_OPCODE_EQ | CMN_OPCODE_1C1)

#define CMN_OPCODE_NEX (CMN_OPCODE_NE | CMN_OPCODE_21)
#define CMN_OPCODE_NEC (CMN_OPCODE_NE | CMN_OPCODE_1C1)

#define CMN_OPCODE_BAX (CMN_OPCODE_BA | CMN_OPCODE_21)
#define CMN_OPCODE_BAC (CMN_OPCODE_BA | CMN_OPCODE_1C1)
#define CMN_OPCODE_BOX (CMN_OPCODE_BO | CMN_OPCODE_21)
#define CMN_OPCODE_BOC (CMN_OPCODE_BO | CMN_OPCODE_1C1)
#define CMN_OPCODE_BXX (CMN_OPCODE_BX | CMN_OPCODE_21)
#define CMN_OPCODE_BXC (CMN_OPCODE_BX | CMN_OPCODE_1C1)

#define CMN_OPCODE_LAX (CMN_OPCODE_LA | CMN_OPCODE_21)
#define CMN_OPCODE_LAC (CMN_OPCODE_LA | CMN_OPCODE_1C1)
#define CMN_OPCODE_LOX (CMN_OPCODE_LO | CMN_OPCODE_21)
#define CMN_OPCODE_LOC (CMN_OPCODE_LO | CMN_OPCODE_1C1)
#define CMN_OPCODE_LXX (CMN_OPCODE_LX | CMN_OPCODE_21)
#define CMN_OPCODE_LXC (CMN_OPCODE_LX | CMN_OPCODE_1C1)

#define CMN_OPCODE_BNO (0x80 | CMN_OPCODE_11)          

#define CMN_OPCODE_ADR (0xf0 | CMN_OPCODE_01)          
#define CMN_OPCODE_INU (0xf8 | CMN_OPCODE_01)          
#define CMN_OPCODE_INP (0xfc | CMN_OPCODE_01)             

// interpreter status codes:
#define CMN_INTERPRETER_END             0x00 ///< end of program reached
#define CMN_INTERPRETER_OK              0x01 ///< execution continues

#define CMN_INTERPRETER_ERROR           0x10 ///< generic error
#define CMN_INTERPRETER_ERROR_THROW     0x11 ///< error raised by ERR instr.

#define CMN_INTERPRETER_ERROR_OPERATION 0x20 ///< bad operation
#define CMN_INTERPRETER_ERROR_ZERODIV   0x21 ///< division by zero
#define CMN_INTERPRETER_ERROR_BAD_CALL  0x22 ///< call of unknown external func.

#define CMN_INTERPRETER_ERROR_MEMORY    0x30 ///< out of memory
#define CMN_INTERPRETER_ERROR_STACK_OF  0x31 ///< memory stack overflow
#define CMN_INTERPRETER_ERROR_CALLSTACK 0x33 ///< call stack overflow/underflow

#define CMN_INTERPRETER_ERROR_BYTECODE  0x40 ///< malformed bytecode
#define CMN_INTERPRETER_ERROR_BC_HEADER 0x41 ///< bad bytecode header
#define CMN_INTERPRETER_ERROR_BC_OPCODE 0x42 ///< invalid opcode
#define CMN_INTERPRETER_ERROR_BC_INSTR  0x43 ///< nonsense instruction data
#define CMN_INTERPRETER_ERROR_BC_JUMP   0x44 ///< jump to nonexistent location

/** Function used by the interpreter to perform I/O. The argument is value to
  print and will be either non-negative and lower than 256 in which case print
  of the value should be performed (and return value doesn't matter), or -1 in
  which case a 1 byte character should be read from input and returned. If a
  character is to be returned from finished input (EOF reached), -1 should be
  returned. */
typedef int16_t (*CMN_IOFunction)(int16_t);

/** Function used by compiler to indicate that a file include command has been
  encountered and that it should be read from. User of the library is supposed
  to implement this function. When the library calls it, it says the specified
  file is to be open and subsequent characters fed to compiler should be from
  that file. If preprocessing is active, the content of each file has to be
  prepended with '[' and appended with ']' (without preprocessor this may or
  may not be done). Once the file has been all read, the library user must NOT
  feed a 0 terminating character to compiler (which would indicate end of whole
  source code), but must simply silently start feeding characters from the
  previously opened file. 0 character must be fed at the very end of the source
  code. If this function is called asking for opening a file that is already
  open above in the include stack (i.e. which would cause a circular include),
  it must be ignored. The string passed as argument won't last after the
  function ends and has to be copied if needed. */
typedef void (*CMN_FileIncludeFunction)(const char *fileName);

struct _CMN_InterpreterS;

/** Function used by interpreter to signal exterunal function calls. The first
  parameter is external function index, the second parameter is pointer to the
  interpreter that calls the function. */
typedef void
  (*CMN_ExternalCallFunction)(uint16_t, struct _CMN_InterpreterS *);

typedef struct _CMN_InterpreterS
{
  const uint8_t *bytecode;
  CMN_NATIVE_UINT *memory0;
  uint8_t *memory8;
  uint16_t *memory16;
  uint32_t *memory32;
  uint32_t memorySize;    ///< number of cells in each type env.
  uint32_t *pointers[4];  ///< pointer tables for each type env.
  const uint8_t *callstack[CMN_INTERPRETER_CALLSTACK_SIZE]; ///< ret. addresses
  uint16_t callStackTop;
  const uint8_t *currentInstruction;
  CMN_IOFunction ioFunction;
  CMN_ExternalCallFunction externalCallFunction;
  uint8_t inputEndReached;
  uint32_t step;
  uint8_t argc;
  const char **argv;
} CMN_Interpreter;

/** Initializes interpreter, returns 1 on success, otherwise 0 (e.g. too little
  memory provided), minCells says the minimum number of memory cells to allocate
  (in case automatic estimation underestimates it), argc and argv are arguments
  passed to the program, argv must not be changed until interpretation ends! */
uint8_t CMN_interpreterInit(CMN_Interpreter *interpreter,
  const uint8_t *bytecode, uint8_t *memory, uint32_t memorySize,
  uint16_t minCells, CMN_IOFunction ioFunction,
  CMN_ExternalCallFunction externalCallFunction, uint8_t argc,
  const char **argv);

/** Executes given number of steps of execution of interpreted program
  (one step ~= one non-empty instruction), returns the state
  (see CMN_INTERPRETER_* ). */
uint8_t CMN_interpreterStep(CMN_Interpreter *interpreter, uint32_t steps);

uint32_t CMN_interpreterGetInstrAddress(const CMN_Interpreter *interpreter);

/** Sets an address in bytecode at which execution will continue next. */
void CMN_interpreterGoto(CMN_Interpreter *interpreter, uint32_t address);

void CMN_interpreterCallFunction(CMN_Interpreter *interpreter,
  uint32_t functionID);

/** Gets a value that's currently on stack top of type environment 0 in
  interpreter's (with possible negative offset). This function doesn't check
  whether such value exists (i.e. if it isn't under address 0) -- in such case
  0 is returned. The value is not popped. */
CMN_NATIVE_UINT CMN_interpretGetValue(CMN_Interpreter *interpreter,
  uint8_t stackTopOffset);

/** Pushes value on stack in type environment 0 of given interpreter. */
void CMN_interpreterPush(CMN_Interpreter *interpreter, CMN_NATIVE_UINT value);

/** Pops n values from type environment 0 of given interpreter. This function
  doesn't check whether this is possible -- as many values as possible will be
  popped. */
void CMN_interpreterPop(CMN_Interpreter *interpreter, uint8_t n);

/** Convenience function which just simply interprets source code passed as
  string, memory and memorySize specify memory used for the whole process
  (bytecode generation, interpreter memory, ...), statusCallback is an optional
  function pointer which if non-zero will be called once with first paramteret
  either 0 (successful end, interpreter pointer passed), 1 (error during
  compileation, second parameter say string position of error) or 2 (error
  during run, interpreter pointer passed), maxSymbols says the maximum amount of
  symbols in symbol table, maxSteps is the maximum number of interpreter steps
  or 0 (infinite). The function returns final value at the stack top in type
  environment 0. */
int CMN_interpretStr(const char *source, uint8_t *memory,
  uint32_t memorySize, uint16_t minCells, uint32_t maxSymbols,
  uint32_t maxSteps, CMN_IOFunction ioFunction,
  void (*statusCallback)(uint8_t, uint32_t, CMN_Interpreter *));

// preprocessor states:
#define CMN_PREPROCESSOR_OK    0
#define CMN_PREPROCESSOR_ERROR 1
#define _CMN_PREPPROCESSOR_OUT 2
#define _CMN_PREPPROCESSOR_IN  3

typedef struct
{
  uint8_t state;
  uint8_t minify; // whether stage 2 output should be minified
  CMN_Tokenizer tokenizer;
  void (*outFunction)(char);
} CMN_Preprocessor;

void CMN_preprocessorInit(CMN_Preprocessor *preprocessor, uint8_t minify,
   void (*outFunction)(char));

/** Feeds an input character to preprocessor. The preprocessor will possibly
  output several characters in return (via the callback function). */
uint8_t CMN_preprocessorFeedChar(CMN_Preprocessor *preprocessor, char c);

/** Estimates how much memory will be needed for the execution of bytecode,
  returns estimated number of memory cells needed for each type environment
  (0 signifies the environment isn't used at all) and an exact number of
  pointers (user ones plus stack top) used in each type environment. This
  can be useful for preallocation of resources. The minStackSize says the
  minimum size of main stack that should be considered, however at least the
  minimum value given by specification will be taken into account. */
void CMN_estimateMemory(const uint8_t *bytecode, uint32_t minStackSize,
  uint32_t memoryCells[4], uint32_t pointers[4]);

static inline uint8_t CMN_instrTypeEnv(const uint8_t *instruction);
void CMN_instrToStr(const uint8_t *instruction, char string[16]);
uint64_t CMN_instrGetConst(const uint8_t *instr);
void CMN_instrGetConsts(const uint8_t *instr, uint64_t *c1, uint64_t *c2);
uint8_t CMN_instrGetConstBits(const uint8_t *instr);
uint8_t CMN_instrTouchesMem(uint8_t opcode);
uint8_t CMN_instrTouchesPtr(uint8_t opcode);

uint8_t CMN_bytecodeChecksum(const uint8_t *bytecode);

/** Removes a continuous block of instructions from bytecode and modifies rest
  of bytecode to keep its semantics (recomputes jump addresses, recomputes
  header checksum, ...). */
void CMN_bytecodeRemoveInstrs(uint8_t *bytecode, uint32_t startAddr,
  uint16_t instrCount);

typedef struct
{
  CMN_Tokenizer tokenizer;
  uint8_t *bytecode;
  const uint8_t *bytecodeLimit;
  uint8_t *bytecodeEnd;
  uint8_t currentTypeEnv;
  uint8_t implicitAddressSize; /**< How many half-bytes are reserved for unknown
                                    addresses, if compilation fails due to
                                    address not fitting, increase this. */
  uint32_t parseStack[CMN_PARSE_STACK_SIZE];
  uint8_t parseStackTop;
  uint8_t state;
  uint8_t flags;
  char *symbolTable;           /**< Symbol table stores pseudohashes of strings
                                    (ptr and func names), each pseudohash has a
                                    type indicated by its first char ('f': func.
                                    def., 'c': func. call, 's': info about
                                    pointer size, 'l': label def., 'j': goto,
                                    'e': external call, '0', '1̈́', '2' and '3':
                                    ptr. in respective type env., 'n': unused).
                                    Each symbol has an index which is given by
                                    its order among same type symbols. */
  uint16_t symbolCount;
  uint16_t symbolTableSize;    ///< Maximum number of items in the table.
  CMN_FileIncludeFunction includeFunction; ///< If 0, includes aren't supported.
} CMN_Compiler;

#define CMN_OPTIMIZE_REMOVE_NOPS   0x00000001 ///< Remove NOP instructions.
#define CMN_OPTIMIZE_REMOVE_DEAD   0x00000002 /**< Remove dead parts of code,
                                                   e.g. unused functions. */
#define CMN_OPTIMIZE_REPLACE_OPS   0x00000004 /**< Replace operations with more
                                                   efficient ones. */
#define CMN_OPTIMIZE_INLINE        0x00000008 ///< Inline functions.
#define CMN_OPTIMIZE_ALL           0xffffffff

/** Applies selected optimizations to bytecode, compiler pointer can optionally
  be passed so that its symbol table is adjusted to match the optimized
  bytecode. */
void CMN_bytecodeOptimize(uint8_t *bytecode, uint32_t types,
  CMN_Compiler *compiler);

#define CMN_BYTECODE_SANITY_OK              0x01 ///< all OK
#define CMN_BYTECODE_SANITY_ERROR           0x02 ///< unspecified error
#define CMN_BYTECODE_SANITY_ERROR_HEADER    0x03 ///< malformed header
#define CMN_BYTECODE_SANITY_ERROR_CHECKSUM  0x04 ///< bad code checksum
#define CMN_BYTECODE_SANITY_ERROR_INSTR     0x05 ///< bad instruction
#define CMN_BYTECODE_SANITY_ERROR_NO_END    0x06 ///< no end instruction

/** Performs a basic sanity check of given bytecode and returns appropriate
  status code. Note that passing this test does not guarantee sanity or
  safety of the bytecode, it just catches most obvious errors. */
uint8_t CMN_bytecodeCheckSanity(const uint8_t *bytecode, uint32_t maxSize);

// compiler status codes:
#define CMN_COMPILER_OK                     0x00
#define CMN_COMPILER_ERROR_BAD_TOKEN        0x01
#define CMN_COMPILER_ERROR_UNEXPECTED_TOKEN 0x02
#define CMN_COMPILER_ERROR_UNEXPECTED_END   0x03
#define CMN_COMPILER_ERROR_BYTECODE_TOO_BIG 0x04
#define CMN_COMPILER_ERROR_UNKNOWN_NAME     0x05
#define CMN_COMPILER_ERROR_REDEFINED        0x06
#define CMN_COMPILER_ERROR_UNSUPPORTED      0x07
#define CMN_COMPILER_ERROR_PARSE_STACK      0x08
#define CMN_COMPILER_ERROR_SYMBOL_TABLE     0x09
#define CMN_COMPILER_ERROR_GENERIC          0xff

void CMN_compilerInit(CMN_Compiler *compiler, uint8_t *bytecode,
  uint32_t bytecodeMaxSize, char *symbolTableMemory, uint32_t symbolTableSize,
  CMN_FileIncludeFunction includeFunction);

/** Feeds a single source code character to the compiler. Note that compiler
  does not perform preprocessing (see the preprocessor struct). The compiler
  potentially generates part of the bytecode, sets it status code and returns
  it. */
uint8_t CMN_compilerFeedChar(CMN_Compiler *compiler, char character);

/** Adds symbol to compiler's symbol table. */
int32_t CMN_compilerAddSymbol(CMN_Compiler *compiler,
  char symbol[CMN_STRING_PSEUDOHASH_SIZE]);

/** Finds symbol by name, returns its index or -1 if not found. */
int32_t CMN_compilerFindSymbol(const CMN_Compiler *compiler,
  char symbol[CMN_STRING_PSEUDOHASH_SIZE]);

/** Given a name of function, returns its index according to symbol table, or
  -1 if match isn't found. This function may only be used after the code has
  been compiled. */
int32_t CMN_compilerFindFunction(const CMN_Compiler *compiler,
  const char *funcName, uint8_t isExternal);

/** Gets symbol with given index and type (index is the sequential number within
  symbols in the same type group). */
uint8_t CMN_compilerGetSymbol(const CMN_Compiler *compiler, char typeChar,
  uint32_t id, char symbol[CMN_STRING_PSEUDOHASH_SIZE]);

//------------------------------------------------------------------------------
// privates:

char _CMN_numPseudohash(uint8_t n)
{
  n %= 64;

  if (n < 2)
    return '_';

  if (n < 12)
    return n + '0' - 2;

  if (n < 38)
    return n + 'a' - 12;

  return n + 'A' - 38;
}

unsigned int _CMN_strLen(const char *s)
{
  unsigned int r = 0;

  while (s[r] != 0)
    r++;

  return r;
}

uint8_t _CMN_typeEnvBits(uint8_t typeEnv)
{
  typeEnv = typeEnv == 0 ? ((uint8_t) sizeof(CMN_NATIVE_UINT)) :
    (typeEnv + (typeEnv == 3));

  return typeEnv * 8;
}

static inline uint8_t CMN_instrTypeEnv(const uint8_t *instruction)
{
  return instruction[1] >> 6;
}

int32_t CMN_unsignedToSigned32(uint32_t value, uint8_t bits)
{
  return (value & (0x00000001 << (bits - 1))) ?
    -1 * ((int32_t) ((((~value) & (0xffffffff >> (32 - bits)))) + 1))
    : ((int32_t) value);
}

int CMN_unsignedToSignedNative(CMN_NATIVE_UINT value)
{
  CMN_NATIVE_UINT tmp = -1;
  tmp /= 2;

  if (value <= tmp)
    return value;

  value = (((CMN_NATIVE_UINT) -1) - value) + 1;
  return -1 * ((int) value);
}

#define _COMP switch (greater | (eq << 1)) {\
    case 0: return v1 < v2; break;\
    case 1: return v1 > v2; break;\
    case 2: return v1 <= v2;  break;\
    case 3: return v1 >= v2; break;\
    default: return 0; break; }

uint8_t _CMN_compare(uint32_t v1, uint32_t v2, uint8_t greater, uint8_t eq)
{ _COMP }

uint8_t _CMN_compareSigned(int32_t v1, int32_t v2, uint8_t greater, uint8_t eq)
{ _COMP }

#undef _COMP

uint64_t _CMN_interpreterGetX(CMN_Interpreter *interpreter, uint8_t typeEnv)
{
  switch (typeEnv)
  {
    case 0: return interpreter->memory0[interpreter->pointers[0][0]]; break;
    case 1: return interpreter->memory8[interpreter->pointers[1][0]]; break;
    case 2: return interpreter->memory16[interpreter->pointers[2][0]]; break;
    case 3: return interpreter->memory32[interpreter->pointers[3][0]]; break;
    default: break;
  }

  return 0;
}

void _CMN_interpreterGetXY(CMN_Interpreter *interpreter, uint8_t typeEnv,
  uint64_t *x, uint64_t *y)
{
  switch (typeEnv)
  {
#define _CASE(n,t,m) \
  case n: {\
  t *p = interpreter->m + interpreter->pointers[n][0];\
  *x = *p; p--; *y = *p;\
  break; }

    _CASE(0,CMN_NATIVE_UINT,memory0)
    _CASE(1,uint8_t,memory8)
    _CASE(2,uint16_t,memory16)
    _CASE(3,uint32_t,memory32)
    default: break;

#undef _CASE
  }
}

uint8_t _CMN_interpreterPopPush(CMN_Interpreter *interpreter, uint8_t typeEnv,
  int8_t pop, uint64_t r)
{
  interpreter->pointers[typeEnv][0] += -1 * pop + 1;

  if (interpreter->pointers[typeEnv][0] >= interpreter->memorySize)
    return 0;

  switch (typeEnv)
  {
    case 0: interpreter->memory0[interpreter->pointers[0][0]] = r;
      break;

    case 1: interpreter->memory8[interpreter->pointers[1][0]] = r % 256;
      break;

    case 2: interpreter->memory16[interpreter->pointers[2][0]] = r % 65536;
      break;

    case 3: interpreter->memory32[interpreter->pointers[3][0]] = r;
      break;

    default: break;
  }

  return 1;
}

void CMN_interpreterGoto(CMN_Interpreter *interpreter, uint32_t address)
{
  interpreter->currentInstruction = interpreter->bytecode + 
    CMN_BYTECODE_HEADER_SIZE + 2 * address;
}

uint32_t CMN_interpreterGetInstrAddress(const CMN_Interpreter *interpreter)
{
  return (interpreter->currentInstruction - interpreter->bytecode -
    CMN_BYTECODE_HEADER_SIZE) / 2;
}

void CMN_interpreterCallFunction(CMN_Interpreter *interpreter,
  uint32_t functionID)
{
  if (interpreter->callStackTop >= CMN_INTERPRETER_CALLSTACK_SIZE - 1)
    return;

  const uint8_t *instr = interpreter->bytecode + CMN_BYTECODE_HEADER_SIZE;

  while (*instr != CMN_OPCODE_END)
  {
    if (instr[0] == CMN_OPCODE_DES && instr[1] == CMN_DES_FUNC)
    {
      if (functionID == 0)
      {
        interpreter->callstack[interpreter->callStackTop] =
          interpreter->currentInstruction;

        interpreter->callStackTop++;
        interpreter->currentInstruction = instr + 4;

        return;
      }
      else
        functionID--;
    }

    instr += 2;
  }
}

uint32_t _CMN_interpreterGetPtrAddr(CMN_Interpreter *interpreter,
  uint8_t typeEnv, uint32_t pointerIndex)
{
  return (pointerIndex <= CMN_LAST_SPECIAL_PTR) ?
    interpreter->pointers[typeEnv][0] - pointerIndex
    : interpreter->pointers[typeEnv][pointerIndex - CMN_LAST_SPECIAL_PTR];
}

uint32_t *_CMN_interpreterGetPtrForWrite(CMN_Interpreter *interpreter,
  uint8_t typeEnv, uint32_t pointerIndex)
{
  uint8_t userPointer = pointerIndex > CMN_LAST_SPECIAL_PTR;

  return (pointerIndex == 0 || userPointer) ?
    &(interpreter->pointers[typeEnv][pointerIndex -
      CMN_LAST_SPECIAL_PTR * userPointer]) : 0;
}

uint8_t CMN_interpreterStep(CMN_Interpreter *interpreter, uint32_t steps)
{
  #define _INSTR interpreter->currentInstruction
  #define _POP(n) \
    if (!(_INSTR[1] & CMN_MASK_INSTR_NOPOP)) { \
      uint32_t *ptrVal = &interpreter->pointers[CMN_instrTypeEnv(_INSTR)][0];\
      *ptrVal -= n;\
      if (*ptrVal >= interpreter->memorySize)\
        return CMN_INTERPRETER_ERROR_STACK_OF;}

  uint8_t infiniteSteps = steps == 0;
  uint8_t repeat = 0; // for skipping instructions that do nothing

  while (infiniteSteps || steps > 0 || repeat)
  {
    repeat = 0;
    uint8_t opcode = _INSTR[0];

    if (opcode > CMN_OPCODE_SPECIALS)
    { // typical stack instructions
      uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);

      uint8_t bitsX = _CMN_typeEnvBits(typeEnv);
      uint8_t bitsY = bitsX;

      uint8_t mode = opcode & CMN_MASK_INSTR_MODE;
      uint64_t x = 0, y = 0, r = 0;
      uint8_t opcodeGroup = opcode & CMN_MASK_INSTR_GROUP;

      int8_t pop =
        (_INSTR[1] & CMN_MASK_INSTR_NOPOP) ? 0 :
        ((mode != CMN_OPCODE_01) + (mode == CMN_OPCODE_21));

      if (mode != CMN_OPCODE_01)
        _CMN_interpreterGetXY(interpreter,typeEnv,&x,&y); 

      if (mode == CMN_OPCODE_1C1)
      {
        y = x;
        x = CMN_instrGetConst(_INSTR);

        if (typeEnv == 0)
          bitsX = 32;
      }

      switch (opcodeGroup)
      {
        case CMN_OPCODE_AD: r = y + x; break;
        case CMN_OPCODE_SU: r = y - x; break; 
        case CMN_OPCODE_MU: r = y * x; break;
        case CMN_OPCODE_EQ: r = y == x; break;
        case CMN_OPCODE_NE: r = y != x; break;
        case CMN_OPCODE_BA: r = y & x; break;
        case CMN_OPCODE_BO: r = y | x; break;
        case CMN_OPCODE_BX: r = y ^ x; break;
        case CMN_OPCODE_LA: r = y && x; break;
        case CMN_OPCODE_LO: r = y || x; break;
        case CMN_OPCODE_LX: r = (y == 0) != (x == 0); break;
       
        case CMN_OPCODE_GR:
        case CMN_OPCODE_GE:
        case CMN_OPCODE_SM:
        case CMN_OPCODE_SE:
          r = _CMN_compare(y,x,!(opcode & 0x08),(opcode & 0x04) != 0);
          break;

        case CMN_OPCODE_GS:
        case CMN_OPCODE_BS:
        case CMN_OPCODE_SS:
        case CMN_OPCODE_LS:
          r = _CMN_compareSigned(CMN_unsignedToSigned32(y,bitsY),
            CMN_unsignedToSigned32(x,bitsX),!(opcode & 0x08),(opcode & 0x04) != 0);
          break;

        case CMN_OPCODE_DI:
        case CMN_OPCODE_DS:
        case CMN_OPCODE_MO:
        case CMN_OPCODE_MS:
          if (x == 0)
            return CMN_INTERPRETER_ERROR_ZERODIV;

          if (opcodeGroup == CMN_OPCODE_DS || opcodeGroup == CMN_OPCODE_MS)
            r = (opcodeGroup == CMN_OPCODE_DS) ?
              (CMN_unsignedToSigned32(y,bitsY) / CMN_unsignedToSigned32(x,bitsX)) :
              (CMN_unsignedToSigned32(y,bitsY) % CMN_unsignedToSigned32(x,bitsX));
          else // unsigned
            r = (opcodeGroup == CMN_OPCODE_DI) ? (y / x) : (y % x);

          break;

        case (CMN_OPCODE_BNO & CMN_MASK_INSTR_GROUP):
          r = ~x;
          break;

        case (CMN_OPCODE_ADR & CMN_MASK_INSTR_GROUP):
          r = interpreter->pointers[typeEnv][0];
          break;

        case (CMN_OPCODE_INU & CMN_MASK_INSTR_GROUP):
          r = !interpreter->inputEndReached;
          break;

        case (CMN_OPCODE_INP & CMN_MASK_INSTR_GROUP):
        {
          int16_t v =
            (interpreter->inputEndReached || interpreter->ioFunction == 0)
              ? 0 : interpreter->ioFunction(-1);

          if (v == -1)
          {
            interpreter->inputEndReached = 1;
            r = 0;
          }
          else
            r = v;

          break;
        }

        default: break;
      }

      if (!_CMN_interpreterPopPush(interpreter,typeEnv,pop,r))
        return CMN_INTERPRETER_ERROR_STACK_OF;
    }
    else // non-typical instructions
    {
      switch (opcode)
      {
        case CMN_OPCODE_CAE:
          if (interpreter->externalCallFunction != 0)
            interpreter->externalCallFunction(CMN_instrGetConst(_INSTR),
              interpreter);
          else
            return CMN_INTERPRETER_ERROR_BAD_CALL;

          break;

        case CMN_OPCODE_POP:
          _POP(CMN_instrGetConst(_INSTR) + 1)
          break;
 
        case CMN_OPCODE_CON:
          if (!_CMN_interpreterPopPush(interpreter,CMN_instrTypeEnv(_INSTR),
            0,CMN_instrGetConst(_INSTR)))
            return CMN_INTERPRETER_ERROR_STACK_OF;

          _POP(1)
          break;

        case CMN_OPCODE_TRA:
          if (!_CMN_interpreterPopPush(interpreter,
            CMN_instrGetConst(_INSTR),1,
            _CMN_interpreterGetX(interpreter,CMN_instrTypeEnv(_INSTR))))
            return CMN_INTERPRETER_ERROR_STACK_OF;

          _POP(1)
          break;

        case CMN_OPCODE_CAL:
          if (interpreter->callStackTop >= CMN_INTERPRETER_CALLSTACK_SIZE - 1)
            return CMN_INTERPRETER_ERROR_CALLSTACK;

          interpreter->callstack[interpreter->callStackTop] = _INSTR;
          interpreter->callStackTop++;

          CMN_interpreterGoto(interpreter,CMN_instrGetConst(_INSTR) - 1);
          break;

        case CMN_OPCODE_RET:
          if (interpreter->callStackTop == 0)
            return CMN_INTERPRETER_ERROR_CALLSTACK;

          _INSTR = interpreter->callstack[interpreter->callStackTop - 1];
          interpreter->callStackTop--;
          break;

        case CMN_OPCODE_INI:
        {
          for (uint8_t i = 0; i < interpreter->argc; ++i)
          {
            const char *c = interpreter->argv[interpreter->argc - 1 - i];
            const char *c2 = c;

            while (*c2 != 0)
              c2++;

            while (c2 >= c)
            {
              interpreter->pointers[0][0]++;
              interpreter->memory0[interpreter->pointers[0][0]] = *c2;
              c2--;
            }
          }

          interpreter->pointers[0][0]++;
          interpreter->memory0[interpreter->pointers[0][0]] =
            interpreter->argc;

          break;
        }

        case CMN_OPCODE_JNA:
        case CMN_OPCODE_JIA:
        {
          uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);

          if (interpreter->pointers[typeEnv][0] >= interpreter->memorySize)
            return CMN_INTERPRETER_ERROR_STACK_OF;

          uint8_t stop = (!_CMN_interpreterGetX(interpreter,
            typeEnv)) == (opcode != CMN_OPCODE_JNA);

          _POP(1);

          if (stop)
            break;
          // else continue to JMA
        }
        __attribute__((fallthrough));
        // ^ gcc extension removing warning, can be removed in case of trouble

        case CMN_OPCODE_JMA:
          CMN_interpreterGoto(interpreter,CMN_instrGetConst(_INSTR) - 1);
          break;

        case CMN_OPCODE_OUT:
        {
          if (interpreter->ioFunction != 0)
          {
            int16_t v = _CMN_interpreterGetX(interpreter,
              CMN_instrTypeEnv(_INSTR));

            interpreter->ioFunction(v >= 0 ? v : 0);
          }

          _POP(1);
          break;
        }

#define _DOINST(cmd)\
  if (typeEnv == 0)\
    { CMN_NATIVE_UINT t,*s = interpreter->memory0 + interpreter->pointers[0][0];\
      (void)(t); cmd;}\
  else if (typeEnv == 1)\
    { uint8_t t,*s = interpreter->memory8 + interpreter->pointers[1][0];\
      (void)(t); cmd;}\
  else if (typeEnv == 2)\
    { uint16_t t,*s = interpreter->memory16 + interpreter->pointers[2][0];\
      (void)(t); cmd;}\
  else\
    { uint32_t t,*s = interpreter->memory32 + interpreter->pointers[3][0];\
      (void)(t); cmd;}\

        case CMN_OPCODE_SWP:
        {
          uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);
          int8_t shift = (_INSTR[1] & CMN_MASK_INSTR_NOPOP) ? 2 : 0;

          _DOINST(t = *s; *(s + shift) = *(s - 1);*(s + shift - 1) = t;)
          interpreter->pointers[typeEnv][0] += shift;
          break;
        }

        case CMN_OPCODE_PCM:
        {
          uint64_t c1, c2;
          uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);
          CMN_instrGetConsts(_INSTR,&c1,&c2);

          c1 = _CMN_interpreterGetPtrAddr(interpreter,typeEnv,c1);
          c2 = _CMN_interpreterGetPtrAddr(interpreter,typeEnv,c2);

          c1 = c1 == c2 ? 0 : (1 + (c1 > c2));

          interpreter->pointers[typeEnv][0]++;

          _DOINST(*s = c1;)
          break;
        }

        case CMN_OPCODE_CND:
        {
          uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);
          int8_t shift = 1 - ((_INSTR[1] & CMN_MASK_INSTR_NOPOP) ? 0 : 3);

          _DOINST(*(s + shift) = *(s - 2) ? *(s - 1) : *s)
          interpreter->pointers[typeEnv][0] += shift;
          break;
        }

        case CMN_OPCODE_PSC:
        case CMN_OPCODE_PAC:
        {
          uint64_t c1, c2;
          uint32_t *p;
          CMN_instrGetConsts(_INSTR,&c1,&c2);

          p = _CMN_interpreterGetPtrForWrite(interpreter,
            CMN_instrTypeEnv(_INSTR),c1);

          if (p != 0)
            *p = (opcode == CMN_OPCODE_PSC) ? c2 : (*p + 
              CMN_unsignedToSigned32(c2,4));

          break;
        }

        case CMN_OPCODE_PAX:
        {
          uint32_t pointer = CMN_instrGetConst(_INSTR);

          uint32_t *p = _CMN_interpreterGetPtrForWrite(interpreter,
            CMN_instrTypeEnv(_INSTR),pointer);

          if (p != 0)
          {
            uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);

            *p += CMN_unsignedToSigned32(_CMN_interpreterGetX(interpreter,
              typeEnv),_CMN_typeEnvBits(typeEnv));

            if (pointer != 0)
              _POP(1);
          }

          break;
        }

        case CMN_OPCODE_PCO:
        {
          uint64_t c1, c2;
          uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);

          CMN_instrGetConsts(_INSTR,&c1,&c2);

          uint32_t *p = _CMN_interpreterGetPtrForWrite(interpreter,typeEnv,c1);

          if (p != 0)
            *p = _CMN_interpreterGetPtrAddr(interpreter,typeEnv,c2);
          else
            return CMN_INTERPRETER_ERROR_OPERATION;

          break;
        }

        case CMN_OPCODE_MEX:
        {
          uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);
          uint64_t val, addr;

          val = _CMN_interpreterGetX(interpreter,typeEnv);
          addr = CMN_instrGetConst(_INSTR);
          addr = _CMN_interpreterGetPtrAddr(interpreter,typeEnv,addr);

          if (addr >= interpreter->memorySize)
            return CMN_INTERPRETER_ERROR_MEMORY;

          if (typeEnv == 0)
            interpreter->memory0[addr] = val;
          else if (typeEnv == 1)
            interpreter->memory8[addr] = val;
          else if (typeEnv == 2)
            interpreter->memory16[addr] = val;
          else
            interpreter->memory32[addr] = val;
            
          _POP(1)
          break;
        }

        case CMN_OPCODE_MGE:
        case CMN_OPCODE_PUX:
        {
          uint8_t typeEnv = CMN_instrTypeEnv(_INSTR);
          uint32_t p;

          p = (opcode == CMN_OPCODE_MGE) ?
            _CMN_interpreterGetPtrAddr(
              interpreter,typeEnv,CMN_instrGetConst(_INSTR))
            :
            (_CMN_interpreterGetPtrAddr(interpreter,typeEnv,0)
              - _CMN_interpreterGetX(interpreter,typeEnv));

          if (opcode == CMN_OPCODE_MGE || (_INSTR[1] & CMN_MASK_INSTR_NOPOP))
            interpreter->pointers[typeEnv][0]++;

          if (p >= interpreter->memorySize)
            return CMN_INTERPRETER_ERROR_STACK_OF;

          if (typeEnv == 0)
            interpreter->memory0[interpreter->pointers[0][0]] =
              interpreter->memory0[p];
          else if (typeEnv == 1)
            interpreter->memory8[interpreter->pointers[1][0]] =
              interpreter->memory8[p];
          else if (typeEnv == 2)
            interpreter->memory16[interpreter->pointers[2][0]] =
              interpreter->memory16[p];
          else
            interpreter->memory32[interpreter->pointers[3][0]] =
              interpreter->memory32[p];

          break;
        }

#undef _DOINST

        case CMN_OPCODE_END: 
          _INSTR -= 2; /* has to be here because even after end API can be used
                          to call a function and that has to return here */
          return CMN_INTERPRETER_END; break;

        case CMN_OPCODE_ERR: return CMN_INTERPRETER_ERROR_THROW; break;

        case CMN_OPCODE_NOP:
        case CMN_OPCODE_DES:
        case CMN_OPCODE_COC:
          repeat = 1;
          break;

        default: return CMN_INTERPRETER_ERROR_BC_OPCODE; break;
      }
    } 

    _INSTR += 2;

    if (!repeat)
    {
      steps--;
      interpreter->step++;
    }
  }

  return CMN_INTERPRETER_OK;

  #undef _POP
  #undef _INSTR
}

void CMN_instrGetConsts(const uint8_t *instr, uint64_t *c1, uint64_t *c2)
{
  uint8_t bits = CMN_instrGetConstBits(instr) / 2;
  *c1 = CMN_instrGetConst(instr); 
  *c2 = (*c1) >> bits;
  *c1 &= ~(0xffffffff << bits);
}

uint64_t CMN_instrGetConst(const uint8_t *instr)
{
  instr++;
  uint64_t result = (*instr) & 0x0f;
  uint8_t shift = 0;
 
  while ((*instr) & CMN_MASK_INSTR_CON)
  {
    instr += 2;
    shift += 4;
    result |= ((uint64_t) ((*instr) & 0x0f)) << shift;
  }

  return result;
}

uint8_t CMN_instrGetConstBits(const uint8_t *instr)
{
  instr++;
  uint8_t result = 4;

  while ((*instr) & CMN_MASK_INSTR_CON)
  {
    instr += 2;
    result += 4;
  }

  return result;
}

uint8_t CMN_interpreterInit(CMN_Interpreter *interpreter,
  const uint8_t *bytecode, uint8_t *memory, uint32_t memorySize,
  uint16_t minCells, CMN_IOFunction ioFunction,
  CMN_ExternalCallFunction externalCallFunction,
  uint8_t argc, const char **argv)
{
  interpreter->bytecode = bytecode;
  interpreter->currentInstruction = bytecode + CMN_BYTECODE_HEADER_SIZE;
  interpreter->ioFunction = ioFunction;
  interpreter->externalCallFunction = externalCallFunction;
  interpreter->inputEndReached = 0;
  interpreter->callStackTop = 0;
  interpreter->memorySize = 0;
  interpreter->step = 0;
  interpreter->argc = argc;
  interpreter->argv = argv;

  uint8_t environments = 0x01; /* We make env 0 be always present, even if no
                                  instructions access it, because it may be
                                  used by the programmer via API functions. */
  uint16_t maxPointers = 0;
  uint32_t mems[4], ptrs[4];
  uint16_t argLen = 1; // for pushing argc

  CMN_estimateMemory(bytecode,minCells,mems,ptrs);

  if (argc > 0) // add space needed for arguments
  {
    for (uint8_t i = 0; i < argc; ++i)
    {
      const char *arg = argv[i];

      argLen++; // terminating 0

      while (*arg != 0)
      {
        argLen++;
        arg++;
      }
    }
  }
    
  mems[0] += argLen;

  for (uint8_t i = 0; i < 4; ++i)
  {
    if (mems[i] != 0 || ptrs[i] != 0)
      environments |= 0x01 << i;

    if (mems[i] > interpreter->memorySize)
      interpreter->memorySize = mems[i];

    if (ptrs[i] > maxPointers)
      maxPointers = ptrs[i];
  }

  uint8_t *pointerEnd = memory;

  interpreter->memory0 = 0;
  interpreter->memory8 = 0;
  interpreter->memory16 = 0;
  interpreter->memory32 = 0;

  for (uint8_t i = 0; i < 4; ++i)
    if (environments & (0x01 << i))
    {
      interpreter->pointers[i] = (uint32_t *) pointerEnd;
      pointerEnd += sizeof(uint32_t) * maxPointers;

#define _DO_SET(m,t)\
  interpreter->m = (t *) pointerEnd;\
  pointerEnd += sizeof(t) * interpreter->memorySize;\
  break;
  
      switch (i)
      {
        case 0: _DO_SET(memory0,CMN_NATIVE_UINT)
        case 1: _DO_SET(memory8,uint8_t)
        case 2: _DO_SET(memory16,uint16_t)
        case 3: _DO_SET(memory32,uint32_t)
        default: break;
      }

#undef _DO_SET
    }
  else
    interpreter->pointers[i] = 0;

  if (pointerEnd - memory > memorySize)
    return 0;

  for (uint32_t i = 0; i != memorySize; ++i)
    memory[i] = 0;

  return 1;
}

CMN_NATIVE_UINT CMN_interpreterGetValue(CMN_Interpreter *interpreter,
  uint8_t stackTopOffset)
{
  return stackTopOffset <= interpreter->pointers[0][0] ?
    interpreter->memory0[interpreter->pointers[0][0] - stackTopOffset] : 0;
}

void CMN_interpreterPush(CMN_Interpreter *interpreter, CMN_NATIVE_UINT value)
{
  if (interpreter->pointers[0][0] >= interpreter->memorySize - 1)
    return;

  interpreter->pointers[0][0]++;
  interpreter->memory0[interpreter->pointers[0][0]] = value;
}

void CMN_interpreterPop(CMN_Interpreter *interpreter, uint8_t n)
{
  interpreter->pointers[0][0] -= n <= interpreter->pointers[0][0] ? n : 0;
}

void CMN_instrToStr(const uint8_t *instruction, char string[16])
{
  static const char names[] =
    // 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
/*0*/ "ENDNOPDESCOCERR      CALCAERETJIAJNAJMA      INI"
/*1*/ "PSCPACPAXPCOMEXMGEPUXPCM      CONCNDSWPTRAPOPOUT"
/*2*/ "ADXADC      SUXSUC      MUXMUC      DIXDICX     "
/*3*/ "DSXDSC      MOXMOC      MSXMSC                  "
/*4*/ "GRXGRC      GEXGEC      SMXSMC      SEXSECX     "
/*5*/ "GSXGSC      BSXBSC      SSXSSC      LSXLSCX     "
/*6*/ "EQXEQC      NEXNEC      BAXBAC      BOXBOCX     "
/*7*/ "BXXBXC      LAXLAC      LOXLOC      LXXLXCX     "
/*8*/ "      BNO                                       "
/*9 - e: empty */
/*f*/ "         ADR                     INU         INP";

  uint16_t nameIndex = *instruction * 3 - (*instruction >= 0x90) * (6 * 3 * 16);

  string[0] = names[nameIndex];
  string[1] = names[nameIndex + 1];
  string[2] = names[nameIndex + 2];
  string[3] = (instruction[1] & CMN_MASK_INSTR_NOPOP) ? '\'' : ' ';
  string[4] = ' ';

  uint8_t env = instruction[1] >> 6;

  env = env * 8 + 8 * (env == 3);

  string[5] = '0' + env / 10; 
  string[6] = '0' + env % 10;
  string[7] = ' ';

  for (uint8_t i = 0; i < 4; ++i)
    string[8 + i] = '0' + ((instruction[1] & (0x08 >> i)) != 0);

  if (instruction[1] & CMN_MASK_INSTR_CON)
  {
    string[12] = '.'; string[13] = '.'; string[14] = '.'; string[15] = 0;
  }
  else
    string[12] = 0;
}

void CMN_tokenizerInit(CMN_Tokenizer *tokenizer)
{
  tokenizer->state = _CMN_TOKENIZER_BLANK;
  tokenizer->tokenStringPos = 0;
}

uint64_t CMN_literalValue(const char *literalString, uint8_t *negative,
  uint8_t *ok)
{
  uint64_t result = 0, prev = 0;
  uint8_t isNegative = 0;
  uint8_t base = 10;  

  if (ok != 0)
    *ok = 1;
 
  if (*literalString == '+' || *literalString == '-')
  {
    isNegative = *literalString == '-';
    literalString++;
  }

  switch (*literalString)
  {
    case 'x': base = 16;
      __attribute__((fallthrough)); // let fall through
    case 'd': literalString++; break;
    case 'b': base = 2; literalString++; break;
    default: break;
  }

  while (*literalString != 0)
  {
    result *= base;

    if (ok != 0 && prev > result) // overflow?
      *ok = 0;

    result += ((*literalString >= '0' && *literalString <= '9') ?
      (*literalString - '0') : (*literalString - 'a' + 10));

    prev = result;
    literalString++;
  }

  if (negative != 0)
    *negative = isNegative;

  return !isNegative ? result : ((0xffffffffffffffff - result) + 1);
}

uint8_t CMN_identifyToken(const char *tokenString)
{
  if (tokenString[0] == '.' && tokenString[1] == 0)
    return CMN_TOKEN_END;
  else if (tokenString[0] == ';' && tokenString[1] == 0)
    return CMN_TOKEN_ELSE;
  else if (tokenString[0] == '?' && 
    (tokenString[1] == 0 || tokenString[1] == '\''))
    return CMN_TOKEN_BRANCH;
  else if (tokenString[0] == '@' &&
    (tokenString[1] == 0 ||
    ((tokenString[1] == '\'' || tokenString[1] == '@')
    && tokenString[2] == 0)))
    return CMN_TOKEN_LOOP;
  else if (tokenString[0] == '!' && tokenString[1] == '@' &&
    tokenString[2] == 0)
    return CMN_TOKEN_BREAK;
  else if (tokenString[0] == '"')
  {
    tokenString++;

    while (1)
    {
      if (tokenString[0] == 0)
        return CMN_TOKEN_ERROR;
      else if (tokenString[0] == '"')
        return (tokenString[1] == 0) ? CMN_TOKEN_STRING : CMN_TOKEN_ERROR;

      tokenString++;
    }
  }
  else if ((tokenString[0] == '+' || tokenString[0] == '-') && 
    ((tokenString[1] <= '9' && tokenString[1] >= '0') ||
      (tokenString[1] <= 'z' && tokenString[1] >= 'a')))
  {
    tokenString++;

    uint8_t base = 1;

    if (tokenString[0] == 'd')
    {
      tokenString++;
    }
    else if (tokenString[0] == 'x')
    {
      base = 2;
      tokenString++;
    }
    else if (tokenString[0] == 'b')
    {
      base = 0;
      tokenString++;
    }

    if (tokenString[0] == 0)
      return CMN_TOKEN_ERROR;

    do
    {
      uint8_t charClass = 0;

      if (tokenString[0] >= 'a' && tokenString[0] <= 'f')
        charClass = 2;
      else if (tokenString[0] >= '0' && tokenString[0] <= '9')
        charClass = tokenString[0] >= '2';
      else
        return CMN_TOKEN_ERROR;

      if (charClass > base)
        return CMN_TOKEN_ERROR;

      tokenString++;
    } while (tokenString[0] != 0);

    return CMN_TOKEN_NUMBER;
  }
  else if (tokenString[0] >= '0' && tokenString[0] <= '9')
  {
    do
    {
      if (tokenString[0] < '0' || tokenString[0] > '9')
        return CMN_TOKEN_ERROR; 

      tokenString++;
    } while (tokenString[0] != 0);

    return CMN_TOKEN_NUMBER;
  }
  else if (tokenString[0] == '~' && tokenString[1] == ':')
  {
    return CMN_identifyToken(tokenString + 2) == CMN_TOKEN_NAME ?
      CMN_TOKEN_LABEL : CMN_TOKEN_ERROR;
  }
  else
  {
    uint8_t result = CMN_TOKEN_NAME;

    do
    {
      if (tokenString[0] <= ' ' || tokenString[0] == '#')
        return CMN_TOKEN_ERROR;
      else if (
        (tokenString[0] > '9' || tokenString[0] < '0') && 
        (tokenString[0] > 'z' || tokenString[0] < 'a') && 
        (tokenString[0] > 'Z' || tokenString[0] < 'A') &&
        tokenString[0] != '_')
        result = (tokenString[0] == ':' && tokenString[1] == 0) ?     
          CMN_TOKEN_FUNC : CMN_TOKEN_COMMAND;

      tokenString++;
    } while (tokenString[0] != 0);

    return result;
  }

  return CMN_TOKEN_ERROR;
}

uint8_t CMN_tokenizerFeedChar(CMN_Tokenizer *tokenizer, char character)
{
  uint8_t append = 0, token = 0;

#define _BLANK(x) (x == ' ' || x == '\n' || x == '\t' || x == ']' || x == '[' || x == 0)

  switch (tokenizer->state)
  {
    case _CMN_TOKENIZER_BLANK:
      if (character == '"')
      {
        tokenizer->state = _CMN_TOKENIZER_STR;
        append = 1;
      }
      else if (character == '#')
        tokenizer->state = _CMN_TOKENIZER_COMMENT;
      else if (!_BLANK(character))
      {
        tokenizer->state = _CMN_TOKENIZER_NAME;
        append = 1;
      }

      break;

    case _CMN_TOKENIZER_NAME:
      if (_BLANK(character))
      {
        tokenizer->state = _CMN_TOKENIZER_BLANK;
        token = 1;
      }
      else if (character == '#')
      {
        tokenizer->state = _CMN_TOKENIZER_COMMENT;
        token = 1;
      }
      else
        append = 1;

      break;

    case _CMN_TOKENIZER_STR_END:
      if (character == '#')
        tokenizer->state = _CMN_TOKENIZER_COMMENT;
      else if (_BLANK(character))
        tokenizer->state = _CMN_TOKENIZER_BLANK;
      else
        tokenizer->state = CMN_TOKENIZER_ERROR;

      break;

    case _CMN_TOKENIZER_COMMENT:
      if (character == '#' || character == '\n')
        tokenizer->state = _CMN_TOKENIZER_BLANK;

      break;

    case _CMN_TOKENIZER_STR:
      append = 1;

      if (character == '"')
      {
        tokenizer->state = _CMN_TOKENIZER_STR_END;
        token = 1;
      }

      break;

    default:
      break;
  }

  if (append)
  {
    if (tokenizer->tokenStringPos < CMN_TOKEN_MAX_LENGTH - 1)
    {
      tokenizer->tokenString[tokenizer->tokenStringPos] = character;
      tokenizer->tokenStringPos++;
    }
    else
      tokenizer->state = CMN_TOKENIZER_ERROR;
  }
  
  if (tokenizer->state == CMN_TOKENIZER_ERROR)
    return CMN_TOKENIZER_ERROR;
  else if (token)
  {
    tokenizer->tokenString[tokenizer->tokenStringPos] = 0;
    tokenizer->tokenStringPos = 0;
    return CMN_TOKENIZER_TOKEN;
  }

  return CMN_TOKENIZER_NOTHING;

  #undef _BLANK
}

void CMN_compilerInit(CMN_Compiler *compiler, uint8_t *bytecode,
  uint32_t bytecodeMaxSize, char *symbolTableMemory, uint32_t symbolTableSize,
  CMN_FileIncludeFunction includeFunction)
{
  CMN_tokenizerInit(&compiler->tokenizer);
  compiler->bytecode = bytecode;
  compiler->bytecodeLimit = bytecode + bytecodeMaxSize;
  compiler->bytecodeEnd = bytecode + CMN_BYTECODE_HEADER_SIZE;
  compiler->currentTypeEnv = 0;
  compiler->implicitAddressSize = 5; // reasonable magic constant
  compiler->parseStackTop = 0;
  compiler->state = CMN_COMPILER_OK;
  compiler->symbolTable = symbolTableMemory;
  compiler->symbolTableSize = symbolTableSize / CMN_STRING_PSEUDOHASH_SIZE;
  compiler->symbolCount = 0;
  compiler->flags = 0;
  compiler->includeFunction = includeFunction;
}

uint8_t _CMN_constSegmentsNeeded(uint64_t c)
{
  uint8_t r = 1;

  while (1)
  {
    c >>= 4;

    if (c == 0)
      break;

    r++;
  }

  return r;
}

uint8_t *_CMN_compilerFillConsts(CMN_Compiler *compiler, uint8_t *address, 
  uint32_t c1, uint32_t c2)
{
  if (compiler != 0 && compiler->state != CMN_COMPILER_OK)
    return address;

  int8_t count1 = _CMN_constSegmentsNeeded(c1),
         count2 = _CMN_constSegmentsNeeded(c2);

  if (count2 > count1)
    count1 = count2;

  for (uint8_t i = 0; i < 2; ++i)
  {
    count2 = count1;
    address[1] &= ~(CMN_MASK_INSTR_CON | 0x0f);

    if (i != 0)
    {
      if (address >= compiler->bytecodeLimit)
      {
        compiler->state = CMN_COMPILER_ERROR_BYTECODE_TOO_BIG;
        return address;
      }

      *address = CMN_OPCODE_COC;
      *(address - 1) |= CMN_MASK_INSTR_CON;
    }

    while (1)
    {
      if (compiler != 0 && address + 3 >= compiler->bytecodeLimit)
      {
        compiler->state = CMN_COMPILER_ERROR_BYTECODE_TOO_BIG;
        return address;
      }

      address++;
      *address |= c1 & 0x0000000f;
      address++;
      count2--;
   
      if (count2 <= 0)
        break;

      c1 >>= 4;

      *(address - 1) |= CMN_MASK_INSTR_CON;
      *address = CMN_OPCODE_COC;
      *(address + 1) = 0;
    }

    c1 = c2;
  }

  return address;
}

/** Fills constant to given bytecode address, potentially adding COCs depending
  on size of the constant, returns the address right after this. */
uint8_t *_CMN_compilerFillConst(CMN_Compiler *compiler, uint8_t *address, 
  uint64_t con)
{
  if (compiler != 0 && compiler->state != CMN_COMPILER_OK)
    return 0;

  address[1] &= ~(CMN_MASK_INSTR_CON | 0x0f);
  int8_t count = _CMN_constSegmentsNeeded(con);

  while (1)
  {
    if (compiler != 0 && address + 3 >= compiler->bytecodeLimit)
    {
      compiler->state = CMN_COMPILER_ERROR_BYTECODE_TOO_BIG;
      return 0;
    }

    address++;
    *address |= con & 0x0000000f;
    address++;
    count--;
    
    if (count <= 0)
      break;

    con >>= 4;

    *(address - 1) |= CMN_MASK_INSTR_CON;
    *address = CMN_OPCODE_COC;
    *(address + 1) = 0;
  }

  return address;
}

void _CMN_compilerParseStackPush(CMN_Compiler *compiler, uint32_t addr)
{
  if (compiler->parseStackTop >= CMN_PARSE_STACK_SIZE)
  {
    compiler->state = CMN_COMPILER_ERROR_PARSE_STACK;
    return;
  }

  compiler->parseStack[compiler->parseStackTop] = addr;
  compiler->parseStackTop++;
}

uint32_t _CMN_compilerPointerToAddr(const CMN_Compiler *compiler,
  const uint8_t *ptr)
{
  return ((ptr - compiler->bytecode) - CMN_BYTECODE_HEADER_SIZE) / 2;
}

uint8_t *_CMN_compilerAddrToPointer(const CMN_Compiler *compiler,
  uint32_t addr)
{
  return compiler->bytecode + CMN_BYTECODE_HEADER_SIZE + 2 * addr;
}

void CMN_pseudohash(char typeChar, const char *str,
  char hash[CMN_STRING_PSEUDOHASH_SIZE])
{
  hash[0] = typeChar;
  uint8_t i = 0;

  while (i < CMN_STRING_PSEUDOHASH_SIZE - 1 && str[i] != 0)
  {
    hash[i + 1] = str[i];
    i++;
  }

  if (i < CMN_STRING_PSEUDOHASH_SIZE - 1)
  {
    while (i < CMN_STRING_PSEUDOHASH_SIZE - 1)
    {
      hash[i + 1] = 0;
      i++;
    }
  }
  else
  {
    uint8_t vlen = 0;
    uint8_t vsum = 0;
    uint8_t vmul = 0;

    while (*str != 0)
    {
      vlen++;
      vsum += *str;
      vmul *= (vmul + 1);
      str++;
    }

    vlen = _CMN_numPseudohash(vlen);
    vsum = _CMN_numPseudohash(vsum);
    vmul = _CMN_numPseudohash(vmul);

    hash[CMN_STRING_PSEUDOHASH_SIZE - 1] = vmul;
    hash[CMN_STRING_PSEUDOHASH_SIZE - 2] = vsum;
    hash[CMN_STRING_PSEUDOHASH_SIZE - 3] = vlen;
  }
}

int32_t CMN_compilerAddSymbol(CMN_Compiler *compiler,
  char symbol[CMN_STRING_PSEUDOHASH_SIZE])
{
  int32_t index = CMN_compilerFindSymbol(compiler,symbol);

  if (index >= 0)
    return index;

  if (compiler->symbolCount >= compiler->symbolTableSize)
  {
    compiler->state = CMN_COMPILER_ERROR_SYMBOL_TABLE;
    return -1;
  }
  
  index = 0;

  char *m = compiler->symbolTable;

  for (uint16_t i = 0; i < compiler->symbolCount; ++i)
  {
    if (m[0] == symbol[0])
      index++;

    m += CMN_STRING_PSEUDOHASH_SIZE;
  }

  for (uint8_t i = 0; i < CMN_STRING_PSEUDOHASH_SIZE; ++i)
    m[i] = symbol[i];

  compiler->symbolCount++;

  return index;
}

uint8_t CMN_compilerGetSymbol(const CMN_Compiler *compiler, char typeChar,
  uint32_t id, char symbol[CMN_STRING_PSEUDOHASH_SIZE])
{
  uint32_t index = 0;

  while (index < compiler->symbolCount)
  {
    if (compiler->symbolTable[index * CMN_STRING_PSEUDOHASH_SIZE] == typeChar)
    {
      if (id == 0)
      {
        for (uint8_t i = 0; i < CMN_STRING_PSEUDOHASH_SIZE; ++i)
          symbol[i] =
            compiler->symbolTable[index * CMN_STRING_PSEUDOHASH_SIZE +  i]; 

        return 1;
      }

      id--;
    }

    index++;
  }

  return 0;
}

int32_t CMN_compilerFindFunction(const CMN_Compiler *compiler,
  const char *funcName, uint8_t isExternal)
{
  char h[CMN_STRING_PSEUDOHASH_SIZE];
  CMN_pseudohash(isExternal ? 'e' : 'f',funcName,h);
  return CMN_compilerFindSymbol(compiler,h);
}

int32_t CMN_compilerFindSymbol(const CMN_Compiler *compiler,
  char symbol[CMN_STRING_PSEUDOHASH_SIZE])
{
  const char *m = compiler->symbolTable;
  int32_t result = 0;

  for (uint32_t i = 0; i < compiler->symbolCount; ++i)
  {
    if (symbol[0] == m[0])
    {
      uint8_t matches = 1;

      for (uint8_t j = 1; j < CMN_STRING_PSEUDOHASH_SIZE; ++j)
        if (symbol[j] != m[j])
        {
          matches = 0;
          break;
        }

      if (matches)
        return result;

      result++;
    }

    m += CMN_STRING_PSEUDOHASH_SIZE;
  }

  return -1;
}

uint8_t *_CMN_compilerFindNthDes(CMN_Compiler *compiler, uint16_t n, uint8_t d)
{
  uint8_t *instr = compiler->bytecode + CMN_BYTECODE_HEADER_SIZE;

  while (1)
  {
    if (*instr == CMN_OPCODE_DES && ((*(instr + 1) & 0x0f) == d))
    {
      if (n == 0)
        break;
      else
        n--;
    }

    instr += 2;
  }

  instr += 2; // skip the DES

  if (d == CMN_DES_FUNC) // with functions also skip the initial jump
  {
    instr += 2;

    while ((*instr == CMN_OPCODE_COC) || (*instr == CMN_OPCODE_NOP))
      instr += 2;
  }

  return instr;
}

void _CMN_decodePtrSizesFromSymbol(uint8_t *typeEnv, uint32_t *ptrIndex,
  uint32_t *ptrSize, const char symbol[CMN_STRING_PSEUDOHASH_SIZE])
{
  *typeEnv = symbol[1] - '0';

  *ptrIndex =   
    symbol[2] - '!' + (symbol[3] - '!') * 64 + (symbol[4] - '!') * 64 * 64;

  *ptrSize =   
    symbol[5] - '!' + (symbol[6] - '!') * 64 + (symbol[7] - '!') * 64 * 64;
}

void _CMN_encodePtrSizeAsSymbol(uint8_t typeEnv, uint32_t ptrIndex,
  uint32_t ptrSize, char symbol[CMN_STRING_PSEUDOHASH_SIZE])
{
  char *c = symbol;

  *c = 's'; c++;
  *c = '0' + typeEnv; c++;

  for (uint8_t i = 0; i < 3; ++i)
  {
    *c = '!' + ptrIndex % 64;
    *(c + 3) = '!' + ptrSize % 64;
    ptrIndex /= 64;
    ptrSize /= 64;
    c++;
  }

  c += 3;

  while (c < symbol + CMN_STRING_PSEUDOHASH_SIZE)
  {
    *c = 0;
    c++;
  } 
}

#define _TOK_STR (compiler->tokenizer.tokenString)
#define _BC_END (compiler->bytecodeEnd)

void _CMN_compilerAppendInstr(CMN_Compiler *compiler, uint8_t opcode,
  uint8_t params)
{
  if (_BC_END >= compiler->bytecodeLimit - 1)
    compiler->state = CMN_COMPILER_ERROR_BYTECODE_TOO_BIG;
  else
  {
    *_BC_END = opcode;
    _BC_END++;
    *_BC_END = params;
    _BC_END++;
  }
}

#define _APPEND_I(opcode,params) \
  _CMN_compilerAppendInstr(compiler,opcode,params);

#define _TYPE_ENV (compiler->currentTypeEnv)

void _CMN_compilerHandleJump(CMN_Compiler *compiler,
  char *token, uint8_t opcode, uint8_t des, char typeChar1, char typeChar2)
{
  char symbol[CMN_STRING_PSEUDOHASH_SIZE];

  CMN_pseudohash(typeChar1,token,symbol);

  int32_t index = CMN_compilerFindSymbol(compiler,symbol);

  if (index >= 0) // destination (func. or label) already declared
  {
    _APPEND_I(opcode,0);

    _BC_END = _CMN_compilerFillConst(compiler,_BC_END - 2,
        _CMN_compilerPointerToAddr(compiler,
          _CMN_compilerFindNthDes(compiler,index,des)));
  }
  else // destination not declared yet, leave address resolution for later
  {
    /* hack: we use the CMN_MASK_INSTR_NOPOP bit to indicate the address
       has not yet been resolved so that we know it later */
    _APPEND_I(opcode,CMN_IPARAMS(0,1,0,0));

    uint8_t *tmp = _BC_END - 2;

    symbol[0] = typeChar2;
    index = CMN_compilerAddSymbol(compiler,symbol);

    for (uint8_t i = 0; i < compiler->implicitAddressSize - 1; ++i)
      _APPEND_I(CMN_OPCODE_NOP,0)

    _CMN_compilerFillConst(compiler,tmp,index); // store the index
  }
}

uint8_t CMN_compilerFeedChar(CMN_Compiler *compiler, char character)
{
#define _CMN_COMPILER_FLAG_INIT_FUNC_NEEDED 1
#define _CMN_COMPILER_FLAG_COMMANDS_STARTED 2

  char symbol[CMN_STRING_PSEUDOHASH_SIZE];

  if (compiler->state != CMN_COMPILER_OK)
    return compiler->state;

  switch (CMN_tokenizerFeedChar(&compiler->tokenizer,character))
  {
    case CMN_TOKENIZER_TOKEN:
    {
      uint8_t token = CMN_identifyToken(_TOK_STR);

      if (!(compiler->flags & _CMN_COMPILER_FLAG_COMMANDS_STARTED) &&
        compiler->parseStackTop == 0 && token != CMN_TOKEN_FUNC)
      {
        // first top-level command found, reserve space for calling init func.

        for (uint8_t i = 0; i < compiler->implicitAddressSize; ++i)
          _APPEND_I(CMN_OPCODE_NOP,i == 0) // hack: use 1 in first NOP as a mark

        compiler->flags |= _CMN_COMPILER_FLAG_COMMANDS_STARTED;
      }

      switch (token)
      {
        case CMN_TOKEN_COMMAND:
        case CMN_TOKEN_BREAK:
        case CMN_TOKEN_BRANCH:
        case CMN_TOKEN_LOOP:
        {
          uint8_t noPop = 0;
          unsigned int len = _CMN_strLen(_TOK_STR);

          if (_TOK_STR[len - 1] == '\'')
          {
            len--;
            noPop = 1;
            _TOK_STR[len] = 0;
          }

#define _STR_ID(a,b,c)\
  ((((uint32_t) (c)) << 24) | (((uint32_t) (b)) << 16) | (a))

          uint32_t sID = len > 3 ? 0 : _STR_ID(
            _TOK_STR[0],
            len > 1 ? _TOK_STR[1] : 0,  
            len > 2 ? _TOK_STR[2] : 0);

          switch (sID)
          {
#define _SIMPLE_OP(c1,c2,c3,opcode,con) case _STR_ID(c1,c2,c3):\
  _APPEND_I(opcode,CMN_IPARAMS(_TYPE_ENV,noPop,0,con)); break;

            _SIMPLE_OP('+',0,0,    CMN_OPCODE_ADX,0)
            _SIMPLE_OP('-',0,0,    CMN_OPCODE_SUX,0)
            _SIMPLE_OP('+','+',0,  CMN_OPCODE_ADC,1)
            _SIMPLE_OP('-','-',0,  CMN_OPCODE_SUC,1)
            _SIMPLE_OP('*',0,0,    CMN_OPCODE_MUX,0)
            _SIMPLE_OP('/',0,0,    CMN_OPCODE_DIX,0)
            _SIMPLE_OP('%',0,0,    CMN_OPCODE_MOX,0)
            _SIMPLE_OP('/','/',0,  CMN_OPCODE_DSX,0)
            _SIMPLE_OP('%','%',0,  CMN_OPCODE_MSX,0)
            _SIMPLE_OP('>','<',0,  CMN_OPCODE_SWP,0)
            _SIMPLE_OP('^',0,0,    CMN_OPCODE_POP,0)
            _SIMPLE_OP('?','?',0,  CMN_OPCODE_CND,0)
            _SIMPLE_OP('&',0,0,    CMN_OPCODE_BAX,0)
            _SIMPLE_OP('|',0,0,    CMN_OPCODE_BOX,0)
            _SIMPLE_OP('|','!',0,  CMN_OPCODE_BXX,0)
            _SIMPLE_OP('&','&',0,  CMN_OPCODE_LAX,0)
            _SIMPLE_OP('|','|',0,  CMN_OPCODE_LOX,0)
            _SIMPLE_OP('|','!','!',CMN_OPCODE_LXX,0)
            _SIMPLE_OP('!','!',0,  CMN_OPCODE_EQC,0)
            _SIMPLE_OP('!',0,0,    CMN_OPCODE_BNO,0)
            _SIMPLE_OP('<','?',0,  CMN_OPCODE_INU,0)
            _SIMPLE_OP('<','-',0,  CMN_OPCODE_INP,0)
            _SIMPLE_OP('-','>',0,  CMN_OPCODE_OUT,0)
            _SIMPLE_OP('$','$',0,  CMN_OPCODE_ADR,0)

            _SIMPLE_OP('=',0,0,    CMN_OPCODE_EQX,0)
            _SIMPLE_OP('!','=',0,  CMN_OPCODE_NEX,0)
            _SIMPLE_OP('<',0,0,    CMN_OPCODE_SMX,0)
            _SIMPLE_OP('<','=',0,  CMN_OPCODE_SEX,0)
            _SIMPLE_OP('>',0,0,    CMN_OPCODE_GRX,0)
            _SIMPLE_OP('>','=',0,  CMN_OPCODE_GEX,0)
            _SIMPLE_OP('<','<',0,  CMN_OPCODE_SSX,0)
            _SIMPLE_OP('<','<','=',CMN_OPCODE_LSX,0)
            _SIMPLE_OP('>','>',0,  CMN_OPCODE_GSX,0)
            _SIMPLE_OP('>','>','=',CMN_OPCODE_BSX,0)

#undef _SIMPLE_OP

            case _STR_ID('~','0',0):   _TYPE_ENV = 0; break;
            case _STR_ID('~','8',0):   _TYPE_ENV = 1; break;
            case _STR_ID('~','1','6'): _TYPE_ENV = 2; break;
            case _STR_ID('~','3','2'): _TYPE_ENV = 3; break;

            case _STR_ID('>','0',0):
            case _STR_ID('>','8',0):
            case _STR_ID('>','1','6'):
            case _STR_ID('>','3','2'):
            {
              uint8_t env = (_TOK_STR[1] > '1') + 2 * (_TOK_STR[2] != 0);

              if (!noPop || env != _TYPE_ENV) // otherwise has no effect
                _APPEND_I(CMN_OPCODE_TRA,CMN_IPARAMS(_TYPE_ENV,noPop,0,env))

              break;
            }

            case _STR_ID('@','@',0):
              _CMN_compilerParseStackPush(compiler,
                _CMN_compilerPointerToAddr(compiler,_BC_END));
              _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_LOOP))
              _APPEND_I(CMN_OPCODE_NOP,0)
              break;

            case _STR_ID('!','.',0):
              _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_EXIT))
              _APPEND_I(CMN_OPCODE_JMA,0)
 
              for (uint8_t i = 0; i < compiler->implicitAddressSize - 1; ++i)
                _APPEND_I(CMN_OPCODE_NOP,0)

              break;

            case _STR_ID('-','-','>'): // -->
            {
              if (noPop)
              {
                compiler->state = CMN_COMPILER_ERROR_BAD_TOKEN;
                return compiler->state;
              }

              const char *cmd = " @' -> . ^ ";

              while (*cmd != 0)
              {
                if (CMN_compilerFeedChar(compiler,*cmd) != CMN_COMPILER_OK)
                  break;

                cmd++;
              }

              break;
            }

            case _STR_ID('@',0,0):
            case _STR_ID('?',0,0):
            case _STR_ID('!','@',0):
              _CMN_compilerParseStackPush(compiler,
                _CMN_compilerPointerToAddr(compiler,_BC_END));

              _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,
                _TOK_STR[0] == '@' ? CMN_DES_LOOP :
                  (_TOK_STR[0] == '?' ? CMN_DES_IF : CMN_DES_LOOP_BREAK)))

              if (_TOK_STR[0] != '!')
                _APPEND_I(CMN_OPCODE_JNA,CMN_IPARAMS(_TYPE_ENV,noPop,0,0))
              else
                _APPEND_I(CMN_OPCODE_JMA,0)

              for (uint8_t i = 0; i < compiler->implicitAddressSize - 1; ++i)
                _APPEND_I(CMN_OPCODE_NOP,0)

              break;

            default:
              if (_TOK_STR[0] == '$')
              {
                if (_TOK_STR[1] == 0)
                {
                  _APPEND_I(CMN_OPCODE_PUX,CMN_IPARAMS(_TYPE_ENV,noPop,0,0));
                  break;
                }

                uint8_t opc = CMN_OPCODE_MGE;
                char *s1 = _TOK_STR + 1;
                char *s2 = 0;

                if (_TOK_STR[1] == '>' || _TOK_STR[1] == '<')
                {
                  opc = CMN_OPCODE_PAC;
                  s1++;
                }
                else if (_TOK_STR[1] == ':')
                {
                  opc = CMN_OPCODE_MEX;
                  s1++;
                }
                else if (_TOK_STR[1] == '+')
                {
                  opc = CMN_OPCODE_PAX;
                  s1++;
                }
                else
                {
                  char *s3 = _TOK_STR + 2;
                  
                  while (*s3 != 0)
                  {
                    if (*s3 == '>' || *s3 == '=')
                    {
                      opc = *s3 == '>' ? CMN_OPCODE_PCO : CMN_OPCODE_PCM;
                      s1 = s3 + 1;
                      s2 = _TOK_STR + 1;
                      *s3 = 0;
                      break;
                    }

                    s3++;
                  }
                }

                int32_t pointer1, pointer2;
                int32_t *p = &pointer1;

                for (uint8_t i = 0; i < 2; ++i)
                {
                  CMN_pseudohash('0' + _TYPE_ENV,s1,symbol);

                  if (s1[1] == 0 && s1[0] >= '0' && s1[0] <= '9')
                    *p = s1[0] - '0';
                  else
                  {
                    *p = CMN_compilerFindSymbol(compiler,symbol);

                    if (*p >= 0)
                      *p += CMN_LAST_SPECIAL_PTR + 1;
                  } 

                  if (*p < 0)
                  {
                    compiler->state = CMN_COMPILER_ERROR_UNKNOWN_NAME;
                    break;
                  }

                  if (s2 == 0)
                    break;

                  s1 = s2;
                  p = &pointer2;
                }

                _APPEND_I(opc,CMN_IPARAMS(_TYPE_ENV,noPop,0,0));

                if (opc == CMN_OPCODE_PAC)
                  _BC_END = _CMN_compilerFillConsts(compiler,_BC_END - 2,
                    pointer1, _TOK_STR[1] == '>' ? 0x01 : 0x0f);
                else if (opc == CMN_OPCODE_PCO || opc == CMN_OPCODE_PCM)
                  _BC_END = _CMN_compilerFillConsts(compiler,_BC_END - 2,
                    pointer1,pointer2);
                else          
                  _BC_END = _CMN_compilerFillConst(compiler,_BC_END - 2,
                    pointer1);
              }
              else if (_TOK_STR[0] == '~')
              {
                if (_TOK_STR[1] == '"')
                {
                  _TOK_STR[len - 1] = 0; // remove the final '"'

                  if (compiler->includeFunction != 0)
                    compiler->includeFunction(_TOK_STR + 2);
                  else
                  {
                    _TOK_STR[len - 1] = '"';
                    compiler->state = CMN_COMPILER_ERROR_UNSUPPORTED;
                    return compiler->state; 
                  }
                }
                else
                { // pointer
                  uint32_t size = 1;
                  char *separator = _TOK_STR;

                  while (*separator != 0 && *separator != ':')
                    separator++;

                  if (*separator == ':')
                  {
                    *separator = 0;

                    if (CMN_identifyToken(separator + 1) != CMN_TOKEN_NUMBER)
                    {
                      compiler->state = CMN_COMPILER_ERROR_BAD_TOKEN;
                      return compiler->state;
                    }

                    size = CMN_literalValue(separator + 1,0,0);
                  }

                  if (CMN_identifyToken(_TOK_STR + 1) != CMN_TOKEN_NAME)
                  {
                    compiler->state = CMN_COMPILER_ERROR_BAD_TOKEN;
                    return compiler->state;
                  }
 
                  CMN_pseudohash('0' + compiler->currentTypeEnv,
                    _TOK_STR + 1,symbol);

                  uint32_t id = CMN_compilerAddSymbol(compiler,symbol);

                  if (size != 0)
                  {
                    /* 0 sized pointers don't need initialization, they aren't
                       supposed to point to allocated memory */
                    compiler->flags |= _CMN_COMPILER_FLAG_INIT_FUNC_NEEDED;

                    _CMN_encodePtrSizeAsSymbol(_TYPE_ENV,id,size,symbol);
                    CMN_compilerAddSymbol(compiler,symbol);
                  }
                }
              }
              else if (_TOK_STR[0] == '>')
              { // goto
                if (CMN_identifyToken(_TOK_STR + 1) == CMN_TOKEN_NAME)
                {
                  _APPEND_I(CMN_OPCODE_DES,CMN_DES_GOTO)

                  _CMN_compilerHandleJump(compiler,_TOK_STR + 1,CMN_OPCODE_JMA,
                    CMN_DES_LABEL,'l','j');
                }
                else
                {
                  compiler->state = CMN_COMPILER_ERROR_BAD_TOKEN;
                  return compiler->state;
                }
              }
              else
                compiler->state = CMN_COMPILER_ERROR_BAD_TOKEN;

              break;
          }

#undef _STR_ID

          break;
        } // case COMMAND, BREAK, BRANCH, LOOP

        case CMN_TOKEN_NAME:
        {
          _CMN_compilerHandleJump(compiler,_TOK_STR,CMN_OPCODE_CAL,CMN_DES_FUNC,
            'f','c');
          break;
        }

        case CMN_TOKEN_LABEL:
          CMN_pseudohash('l',_TOK_STR + 2,symbol);

          if (CMN_compilerFindSymbol(compiler,symbol) >= 0)
          {
            compiler->state = CMN_COMPILER_ERROR_REDEFINED;
            return compiler->state;
          }

          CMN_compilerAddSymbol(compiler,symbol);
          _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_LABEL))
          break;

        case CMN_TOKEN_FUNC:
        {
          uint8_t p = 0;

          while (compiler->tokenizer.tokenString[p] != 0)
          {
            if (compiler->tokenizer.tokenString[p] == ':')
            {
              compiler->tokenizer.tokenString[p] = 0;
              break;
            }

            p++;
          }

          CMN_pseudohash('f',compiler->tokenizer.tokenString,symbol);

          if (CMN_compilerFindSymbol(compiler,symbol) >= 0)
          {
            compiler->state = CMN_COMPILER_ERROR_REDEFINED;
            break;
          }

          CMN_compilerAddSymbol(compiler,symbol);

          if (compiler->parseStackTop != 0)
          {
            // function def. must appear always on top level
            compiler->state = CMN_COMPILER_ERROR_UNEXPECTED_TOKEN;
            break;
          }

          _CMN_compilerParseStackPush(compiler,
            _CMN_compilerPointerToAddr(compiler,_BC_END));

          _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_FUNC))
          _APPEND_I(CMN_OPCODE_JMA,0)

          for (uint8_t i = 0; i < compiler->implicitAddressSize - 1; ++i)
            _APPEND_I(CMN_OPCODE_NOP,0)

          break;
        }

        case CMN_TOKEN_NUMBER:
        {
          _APPEND_I(CMN_OPCODE_CON,CMN_IPARAMS(_TYPE_ENV,1,0,0));

          uint8_t negative, ok;
          uint64_t v = CMN_literalValue(_TOK_STR,&negative,&ok);

          if (!ok)
          {
            compiler->state = CMN_COMPILER_ERROR_UNSUPPORTED;
            return compiler->state;
          }

          if (compiler->currentTypeEnv == 1)
            v &= 0xff;
          else if (compiler->currentTypeEnv == 2)
            v &= 0xffff;

          if (compiler->currentTypeEnv == 0 && negative)
          {
            /* In type env 0 we don't know the bit width so we push negative
            literals by pushing 0 and subtracting constant with SUC. */

            _BC_END = _CMN_compilerFillConst(compiler,_BC_END - 2,0);            
            v = 0xffffffffffffffff - v + 1;
            _APPEND_I(CMN_OPCODE_SUC,CMN_IPARAMS(0,0,0,0));
            _BC_END = _CMN_compilerFillConst(compiler,_BC_END - 2,v);
          }
          else
            _BC_END = _CMN_compilerFillConst(compiler,_BC_END - 2,v);

          break;
        }

        case CMN_TOKEN_STRING:
        {
          const char *c = _TOK_STR + 1;
 
          while (*c != 0 && *c != '"')
            c++;

          c--;

          while (c > _TOK_STR && compiler->state == CMN_COMPILER_OK)
          {
            _APPEND_I(CMN_OPCODE_CON,CMN_IPARAMS(_TYPE_ENV,1,0,0));
            _BC_END = _CMN_compilerFillConst(compiler,_BC_END - 2,*c);
            c--;
          }

          break;
        }

        case CMN_TOKEN_ELSE:
        case CMN_TOKEN_END:
        {
          uint32_t parseStackTopOld = compiler->parseStackTop;            
          uint8_t *matchingInstr = 0; 
          uint8_t instrType;

          // find matching instr., skip possible loop breaks on stack:
          while (1)
          { 
            if (compiler->parseStackTop == 0)
            {
              compiler->state = CMN_COMPILER_ERROR_UNEXPECTED_TOKEN;
              matchingInstr = 0;
              break;
            }

            compiler->parseStackTop--;

            matchingInstr = _CMN_compilerAddrToPointer(compiler,
              compiler->parseStack[compiler->parseStackTop]);

            instrType = (*(matchingInstr + 1)) & 0x0f;

            if (instrType != CMN_DES_LOOP_BREAK)
              break;
          }

          if (matchingInstr == 0)
            break;

          switch (instrType)
          {
            case CMN_DES_LOOP:
            {
              if (token != CMN_TOKEN_END)
              {
                // "else" matched a loop start: error
                compiler->state = CMN_COMPILER_ERROR_UNEXPECTED_TOKEN;
                return compiler->state;
              }

              _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_LOOP_END));
              _APPEND_I(CMN_OPCODE_JMA,0);

              _BC_END = _CMN_compilerFillConst(compiler,_BC_END - 2,
                _CMN_compilerPointerToAddr(compiler,matchingInstr) + 1);

              uint32_t addrHere = 
                _CMN_compilerPointerToAddr(compiler,_BC_END);

              // for non-infinite loop fill back the jump address:
              if (*(matchingInstr + 2) != CMN_OPCODE_NOP)
                _CMN_compilerFillConst(compiler,matchingInstr + 2,addrHere);

              // also fill in addresses for all loop breaks:
              while (1)
              {
                parseStackTopOld--;

                if (parseStackTopOld == compiler->parseStackTop)
                  break;
   
                _CMN_compilerFillConst(compiler,
                  _CMN_compilerAddrToPointer(compiler,
                    compiler->parseStack[parseStackTopOld]) + 2,
                  addrHere);
              }

              break;
            }

            case CMN_DES_ELSE: 
              if (token == CMN_TOKEN_ELSE)
              {
                // else matching another else: error
                compiler->state = CMN_COMPILER_ERROR_UNEXPECTED_TOKEN;
                return compiler->state;
              }
              // else continue on
              __attribute__((fallthrough));

            case CMN_DES_IF:
              if (token == CMN_TOKEN_ELSE)
              {
                // here we just replace the if with else on stack:
                compiler->parseStack[compiler->parseStackTop] =
                  _CMN_compilerPointerToAddr(compiler,_BC_END);
                compiler->parseStackTop = parseStackTopOld;

                _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_ELSE));
                _APPEND_I(CMN_OPCODE_JMA,0);

                for (uint8_t i = 0; i < compiler->implicitAddressSize - 1; ++i)
                  _APPEND_I(CMN_OPCODE_NOP,0)
              }
              else
              {
                _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_IF_END));

                // now pop the if while keeping possible loop breaks above
                while (compiler->parseStackTop < parseStackTopOld - 1)
                {

                  compiler->parseStack[compiler->parseStackTop] =
                    compiler->parseStack[compiler->parseStackTop + 1];

                  compiler->parseStackTop++;
                }
              }

              _CMN_compilerFillConst(compiler,matchingInstr + 2,
                _CMN_compilerPointerToAddr(compiler,_BC_END + 1));

              break;

            case CMN_DES_FUNC:
              compiler->parseStackTop = 0;
              _APPEND_I(CMN_OPCODE_RET,0);

              _CMN_compilerFillConst(compiler,matchingInstr + 2,
                _CMN_compilerPointerToAddr(compiler,_BC_END));

              break;

            default: // unknown description, shouldn't happen
              compiler->state = CMN_COMPILER_ERROR_GENERIC;
              return compiler->state;
              break;
          }
        
          break;
        }

        default:
          compiler->state = CMN_COMPILER_ERROR_BAD_TOKEN; break;
          return compiler->state;
          break;
      }

      break;
    }

    case CMN_TOKENIZER_ERROR:
      compiler->state = CMN_COMPILER_ERROR_BAD_TOKEN;
      return compiler->state;
      break;

    default: break;
  }

  if (compiler->state != CMN_COMPILER_OK)
    return compiler->state;

  if (character == 0) // end of source code => append epilogue code 
  {
    if (compiler->parseStackTop != 0)
    {
      compiler->state = CMN_COMPILER_ERROR_UNEXPECTED_END;
      return compiler->state;
    }

    uint8_t *initFunc = 0;

    if (compiler->flags & _CMN_COMPILER_FLAG_INIT_FUNC_NEEDED)
    {
      // create the init function to set the initial pointer addresses

      _APPEND_I(CMN_OPCODE_DES,CMN_IPARAMS(0,0,0,CMN_DES_FUNC))

      initFunc = _BC_END;

      _APPEND_I(CMN_OPCODE_JMA,0)

      for (uint8_t i = 0; i < compiler->implicitAddressSize - 1; ++i)
        _APPEND_I(CMN_OPCODE_NOP,0)

      const char *symbolItem = compiler->symbolTable;

      uint32_t memoryEnds[4];

      for (uint8_t i = 0; i < 4; ++i)
        memoryEnds[i] = 0;

      for (uint32_t i = 0; i < compiler->symbolCount; ++i)
      {
        if (symbolItem[0] == 's')
        {
          uint8_t env;
          uint32_t ptrIndex, ptrSize;

          _CMN_decodePtrSizesFromSymbol(&env,&ptrIndex,&ptrSize,symbolItem);

          if (ptrSize != 0 && memoryEnds[env] != 0)
          {
            ptrIndex += CMN_LAST_SPECIAL_PTR + 1; // user pointers start here

            _APPEND_I(CMN_OPCODE_PSC,CMN_IPARAMS(env,0,0,0))
            _BC_END = _CMN_compilerFillConsts(compiler,_BC_END - 2,
              ptrIndex,memoryEnds[env]);
          }
            
          memoryEnds[env] += ptrSize;
        }

        symbolItem += CMN_STRING_PSEUDOHASH_SIZE;
      }

      if (compiler->state != CMN_COMPILER_OK)
        return compiler->state;

      for (uint8_t i = 0; i < 4; ++i) // and potentially init stack tops
        if (memoryEnds[i] != 0)
        {
          _APPEND_I(CMN_OPCODE_PSC,CMN_IPARAMS(i,0,0,0))
            
          _BC_END = _CMN_compilerFillConsts(compiler,_BC_END - 2,0,
            memoryEnds[i]);
        }

      _APPEND_I(CMN_OPCODE_INI,0)
      _APPEND_I(CMN_OPCODE_RET,0)

      _CMN_compilerFillConst(compiler,initFunc,
        _CMN_compilerPointerToAddr(compiler,_BC_END));
    }
  
    if (compiler->state != CMN_COMPILER_OK)
      return compiler->state;

    uint8_t *instr = compiler->bytecode + CMN_BYTECODE_HEADER_SIZE; 

    while (*instr != CMN_OPCODE_END) // fill back the init function call
    {
      if (*instr == CMN_OPCODE_NOP && *(instr + 1) == 1)
      {
        *(instr + 1) = 0;

        if (initFunc != 0)
        {       
          *instr = CMN_OPCODE_CAL;

          _CMN_compilerFillConst(compiler,instr,
            _CMN_compilerPointerToAddr(compiler,
              initFunc + 2 * compiler->implicitAddressSize));
        }
        else
          *instr = CMN_OPCODE_INI;

        break;
      }

      instr += 2;
    }
    
    _APPEND_I(CMN_OPCODE_END,0); // append the final end

    if (compiler->state == CMN_COMPILER_OK)
    {
      // do a forward pass and fill the unknown fun. call/goto addresses:

      instr = compiler->bytecode + CMN_BYTECODE_HEADER_SIZE;

      while (*instr != CMN_OPCODE_END)
      {
        if ((*instr == CMN_OPCODE_CAL || *instr == CMN_OPCODE_JMA) &&
          (*(instr + 1) & CMN_MASK_INSTR_NOPOP))
        {
          uint8_t funcCall = *instr == CMN_OPCODE_CAL;
          int32_t c = CMN_instrGetConst(instr);

          *(instr + 1) &= ~CMN_MASK_INSTR_NOPOP;

          CMN_compilerGetSymbol(compiler,funcCall ? 'c' : 'j',c,symbol);

          symbol[0] = funcCall ? 'f' : 'l';

          c = CMN_compilerFindSymbol(compiler,symbol);

          if (c >= 0)
          {
            *(instr + 1) = 0;

            for (uint8_t i = 1; i < compiler->implicitAddressSize; ++i)
            {
              *(instr + 2 * i) = CMN_OPCODE_NOP;
              *(instr + 2 * i + 1) = 0;
            }

            _CMN_compilerFillConst(compiler,instr,
              _CMN_compilerPointerToAddr(compiler,
                _CMN_compilerFindNthDes(compiler,c,
                  funcCall ? CMN_DES_FUNC : CMN_DES_LABEL)));
          }
          else
          {
            if (funcCall)
              *instr = CMN_OPCODE_CAE;
            else
            {
              // undefined label
              compiler->state = CMN_COMPILER_ERROR_UNKNOWN_NAME;
              return compiler->state;
            }
          }
        }
  
        instr += 2;
      } // while (resolve addresses)
      
      instr = compiler->bytecode + CMN_BYTECODE_HEADER_SIZE;

      // now do a forward pass again and order external calls from 0:

      uint16_t nextIndex = 0;

      while (*instr != CMN_OPCODE_END)
      {
        if (*instr == CMN_OPCODE_CAE)
        {
          uint32_t c = CMN_instrGetConst(instr);

          if (c > nextIndex)
          {
            uint8_t *instr2 = instr;

            while (*instr2 != CMN_OPCODE_END)
            {
              if (*instr2 == CMN_OPCODE_CAE)
              {
                uint32_t c2 = CMN_instrGetConst(instr2);

                if (c2 == c)
                {
                  *(instr2 + 1) = 0;

                  for (uint8_t i = 1; i < compiler->implicitAddressSize; ++i)
                  {
                    *(instr2 + 2 * i) = CMN_OPCODE_NOP;
                    *(instr2 + 2 * i + 1) = 0;
                  }
              
                  _CMN_compilerFillConst(compiler,instr2,nextIndex);
                }
              }

              instr2 += 2;
            }

            nextIndex++;
          }
          else if (c == nextIndex)
            nextIndex = c + 1;
        }

        instr += 2;
      }
    
      if (compiler->state != CMN_COMPILER_OK)
        return compiler->state;

      // now do a backwards pass and fill in the exit comm. addresses:

      uint32_t funcEndAddr = 0;
      uint32_t endAddr = _CMN_compilerPointerToAddr(compiler,_BC_END) - 1;
 
      while (instr >= compiler->bytecode + CMN_BYTECODE_HEADER_SIZE)
      {
        if (instr[0] == CMN_OPCODE_RET)
          funcEndAddr = _CMN_compilerPointerToAddr(compiler,instr);
        else if (instr[0] == CMN_OPCODE_DES)
        {
          if (instr[1] == CMN_DES_FUNC)
            funcEndAddr = 0;
          else if (instr[1] == CMN_DES_EXIT)
            _CMN_compilerFillConst(compiler,instr + 2,
              funcEndAddr != 0 ? funcEndAddr : endAddr);
        }

        instr -= 2;
      }
    
      if (compiler->state != CMN_COMPILER_OK)
        return compiler->state;

      // now mark external calls also in the symbol table:

      for (uint32_t i = 0; i < compiler->symbolCount; ++i)
      {
        char *s = compiler->symbolTable + i * CMN_STRING_PSEUDOHASH_SIZE;

        if (s[0] == 'c')
        {
          char s2[CMN_STRING_PSEUDOHASH_SIZE];

          s2[0] = 'f';

          for (uint8_t j = 1; j < CMN_STRING_PSEUDOHASH_SIZE; ++j)
            s2[j] = s[j];

          if (CMN_compilerFindSymbol(compiler,s2) < 0)
            s[0] = 'e'; // no corresponding 'f' symbol => external call
        }
      }

      // fill the header:

      compiler->bytecode[0] = 'C';
      compiler->bytecode[1] = 'B';

      for (uint8_t i = 2; i < 8; ++i)
        compiler->bytecode[i] = 0;

      compiler->bytecode[CMN_BYTECODE_CHECKSUM_BYTE] =
        CMN_bytecodeChecksum(compiler->bytecode);
    } // if (compiler ok)
  } // if (character == 0)
  
  return compiler->state;

#undef _TYPE_ENV
#undef _TOK_STR
#undef _APPEND_I
#undef _BC_END

#undef _CMN_COMPILER_FLAG_INIT_FUNC_NEEDED
#undef _CMN_COMPILER_FLAG_COMMANDS_STARTED
}

uint8_t CMN_instrTouchesMem(uint8_t opcode)
{
  return opcode > CMN_OPCODE_RET && opcode != CMN_OPCODE_PCO &&
    opcode != CMN_OPCODE_PAC && opcode != CMN_OPCODE_PSC &&
    opcode != CMN_OPCODE_JMA;
}

uint8_t CMN_instrTouchesPtr(uint8_t opcode)
{
  return (opcode >= CMN_OPCODE_PSC && opcode <= CMN_OPCODE_PUX);
}

void CMN_estimateMemory(const uint8_t *bytecode, uint32_t minStackSize,
  uint32_t memoryCells[4], uint32_t pointers[4])
{
  if (minStackSize < CMN_MINIMUM_STACK_SIZE)
    minStackSize = CMN_MINIMUM_STACK_SIZE;

  uint16_t stackTops[4];

  bytecode += CMN_BYTECODE_HEADER_SIZE;

  for (uint8_t i = 0; i < 4; ++i)
  {
    memoryCells[i] = 0;
    pointers[i] = 0;
    stackTops[i] = 0;
  }

  while (*bytecode != CMN_OPCODE_END)
  {
    uint8_t typeEnv = CMN_instrTypeEnv(bytecode);

    if (CMN_instrTouchesMem(*bytecode))
    {
      memoryCells[typeEnv]++;

      if (*bytecode == CMN_OPCODE_TRA)
        memoryCells[CMN_instrGetConst(bytecode)]++;
    }
    else if (*bytecode == CMN_OPCODE_PSC)
    {
      uint64_t c1, c2;

      CMN_instrGetConsts(bytecode,&c1,&c2);

      if (c2 > stackTops[typeEnv])
        stackTops[typeEnv] = c2;
    }

    int64_t pIndex = -1, pIndex2 = -1;

    if ( // pointer in C1
      *bytecode == CMN_OPCODE_PSC || *bytecode == CMN_OPCODE_PAC)
    {
      CMN_instrGetConsts(bytecode,(uint64_t *) &pIndex,(uint64_t *) &pIndex2);
    }
    else if ( // pointer in C
      *bytecode == CMN_OPCODE_PAX || *bytecode == CMN_OPCODE_MEX ||
      *bytecode == CMN_OPCODE_MGE)
    {
      pIndex = CMN_instrGetConst(bytecode);
    }
    else if ( // pointer in C1 and C2
      *bytecode == CMN_OPCODE_PCO)
    {
      CMN_instrGetConsts(bytecode,(uint64_t *) &pIndex,(uint64_t *) &pIndex2);

      if (pIndex2 > pIndex)
        pIndex = pIndex2;
    }

    if (pIndex > CMN_LAST_SPECIAL_PTR)
    {
      pIndex -= CMN_LAST_SPECIAL_PTR;

      if (pIndex > ((int32_t) pointers[typeEnv]))
        pointers[typeEnv] = pIndex; 
    }

    bytecode += 2;
  }

  for (uint8_t i = 0; i < 4; ++i)
    if (memoryCells[i] != 0)
    {
      memoryCells[i] = stackTops[i] +
        (memoryCells[i] > minStackSize ? memoryCells[i] : minStackSize);

      pointers[i]++; // add stack top
    }
}

void CMN_bytecodeRemoveInstrs(uint8_t *bytecode, uint32_t startAddr,
  uint16_t instrCount)
{
  uint8_t *instr = bytecode + CMN_BYTECODE_HEADER_SIZE + startAddr * 2;

  do // shift 
  {
    instr[0] = instr[instrCount * 2];
    instr[1] = instr[instrCount * 2 + 1];

    instr += 2;
  } while (*instr != CMN_OPCODE_END);

  instr = bytecode + CMN_BYTECODE_HEADER_SIZE;

  while (*instr != CMN_OPCODE_END) // recompute addresses
  {
    if (*instr == CMN_OPCODE_CAL || // deals with addresses?
      (*instr >= CMN_OPCODE_JIA && *instr <= CMN_OPCODE_JMA))
    {
      uint32_t jumpAddr = CMN_instrGetConst(instr);

/* TODO: possibly change this to also handle the case someone jumps
  inside the removed code (if jump addr is inside the removed block, set
  new addr to the start of the removed block) */

      if (jumpAddr >= startAddr + instrCount)
      {
        jumpAddr -= instrCount;

        uint8_t *tmp = instr + 2;

        while (*tmp == CMN_OPCODE_COC)
        {
          tmp[0] = CMN_OPCODE_NOP;
          tmp[1] = 0;
          tmp += 2;
        }

        _CMN_compilerFillConst(0,instr,jumpAddr);
      }
    }

    instr += 2;
  }

  bytecode[CMN_BYTECODE_CHECKSUM_BYTE] = CMN_bytecodeChecksum(bytecode);
}

uint8_t CMN_bytecodeChecksum(const uint8_t *bytecode)
{
  uint8_t r = 0;

  bytecode += CMN_BYTECODE_HEADER_SIZE;

  while (*bytecode != CMN_OPCODE_END)
  {
    r += bytecode[0];
    r += bytecode[1];
    bytecode += 2;
  }

  return r;
}

void CMN_bytecodeOptimize(uint8_t *bytecode, uint32_t types,
  CMN_Compiler *compiler)
{
#define _ITERATIONS 3 // how many times repeat some kind of processing

  if (types & CMN_OPTIMIZE_REPLACE_OPS)
  {
    uint8_t *instr = bytecode + CMN_BYTECODE_HEADER_SIZE;

    while (*instr != CMN_OPCODE_END)
    {
      // replace "push X, ??X" with "??C, CON X"
      if (instr[0] == CMN_OPCODE_CON && !(instr[1] & CMN_MASK_INSTR_CON) &&
          (instr[1] & CMN_MASK_INSTR_NOPOP) &&
          instr[2] > CMN_OPCODE_SPECIALS &&
          ((instr[2] & 0x03) == CMN_OPCODE_21) &&
          !(instr[3] & CMN_MASK_INSTR_NOPOP))
      {
        /* note: if the constant continues with COCs, we can't do this because
           the instructions won't fit, ALSO doing this with bigger constants
           would lead to sign issues in type env. 0 (where we don't know the
           number bit width -- here we just suppose it's bigger than 4). */

        instr[0] = (instr[2] & (~0x03)) | CMN_OPCODE_1C1;
        instr[1] &= ~CMN_MASK_INSTR_NOPOP;

        instr[2] = CMN_OPCODE_CON;
        instr[3] = instr[1];

        if ((((instr[1] & 0x0f) == 0) && // operations that do nothing
            (instr[0] == CMN_OPCODE_ADC || instr[0] == CMN_OPCODE_SUC ||
            instr[0] == CMN_OPCODE_BOC || instr[0] == CMN_OPCODE_LOC)) ||
          (((instr[1] & 0x0f) == 1) &&
            (instr[0] == CMN_OPCODE_MUC || instr[0] == CMN_OPCODE_DIC ||
            instr[0] == CMN_OPCODE_LAC || instr[0] == CMN_OPCODE_DSC)))
        {
          instr[0] = CMN_OPCODE_NOP;
          instr[1] = 0;
        }
      }
      else if (instr[0] == CMN_OPCODE_PAC && (instr[1] & CMN_MASK_INSTR_CON) &&
        !(instr[3] & CMN_MASK_INSTR_CON))
      {
        if ((instr[1] & 0x0f) != 0) // "PAC 1 to 15" does nothing
        {
          instr[0] = CMN_OPCODE_NOP;
          instr[1] = 0;
          instr[2] = CMN_OPCODE_NOP;
          instr[3] = 0;
        }
        else if ((instr[3] & 0x0f) == 0x0f) // "PAC 0 1" -> "POP"
        {
          instr[0] = CMN_OPCODE_POP;
          instr[1] &= ~(CMN_MASK_INSTR_CON | 0x0f);
          instr[2] = CMN_OPCODE_NOP;
          instr[3] = 0; 
        }
      }

      /* now we simply collapse blocks of at most 16 pops into one pop of
         multiple values (it could be done much better, this is just KISS) */
      int popsInRow = 0;

      while (instr[2 * popsInRow] == CMN_OPCODE_POP &&
        (instr[2 * popsInRow + 1] & 0x0f) == 0 && popsInRow < 16)
        popsInRow++;

      if (popsInRow > 1)
      {
        for (int i = 1; i < popsInRow; ++i)
        {
          instr[2 * i] = CMN_OPCODE_NOP;
          instr[2 * i + 1] = 0;
        }
 
        instr[1] = (instr[1] & 0xf0) | ((popsInRow - 1) & 0x0f);
      }

      instr += 2;
    }
  }

  if (types & CMN_OPTIMIZE_REMOVE_NOPS)
  {
    uint8_t iterations = _ITERATIONS;

    while (iterations)
    {
      uint8_t stop = 1;
      uint32_t addr = 0;

      while (bytecode[CMN_BYTECODE_HEADER_SIZE + 2 * addr] != CMN_OPCODE_END)
      {
        stop = 0;
        uint16_t nopCount = 0;

        while (bytecode[CMN_BYTECODE_HEADER_SIZE + 2 * (addr + nopCount)] ==
          CMN_OPCODE_NOP)
          nopCount++;

        if (nopCount)
          CMN_bytecodeRemoveInstrs(bytecode,addr,nopCount);

        addr++;
      }

      if (stop)
        break;

      iterations--;
    }
  }

  if (types & CMN_OPTIMIZE_INLINE)
  {
    uint8_t *instr = bytecode + CMN_BYTECODE_HEADER_SIZE;

    while (*instr != CMN_OPCODE_END)
    {
      if (*instr == CMN_OPCODE_CAL)
      {
        uint8_t callLen = 0, funLen = 0;
        const uint8_t *instr2 = bytecode + CMN_BYTECODE_HEADER_SIZE +
          CMN_instrGetConst(instr) * 2;

        while (instr[callLen * 2 + 1] & CMN_MASK_INSTR_CON)
          callLen++;

        callLen++;

        while (instr2[funLen * 2] != CMN_OPCODE_RET)
          funLen++;

        if (funLen <= callLen) // will it fit?
        {
          funLen = 0;

          while (instr2[2 * funLen] != CMN_OPCODE_RET)
          {
            instr[2 * funLen] = instr2[2 * funLen];
            instr[2 * funLen + 1] = instr2[2 * funLen + 1];
            funLen++;
          }

          while (funLen < callLen)
          {
            instr[2 * funLen] = CMN_OPCODE_NOP;
            instr[2 * funLen + 1] = 0;
            callLen--;
          }
        }
      }

      instr += 2;
    }
  }

  if (types & CMN_OPTIMIZE_REMOVE_DEAD)
  {
    for (uint8_t i = 0; i < _ITERATIONS; ++i)
    {
      uint32_t addr = 0;
      const uint8_t *instr = bytecode + CMN_BYTECODE_HEADER_SIZE;
      uint16_t funcIndex = 0;

      while (*instr != CMN_OPCODE_END)
      {
        // TODO: remove other unused code, e.g. if 0 etc.

        if (instr[0] == CMN_OPCODE_DES && instr[1] == CMN_DES_FUNC)
        {
          uint32_t funcLen = 0;

          while (instr[2 * funcLen] != CMN_OPCODE_RET)
            funcLen++;

          funcLen++;

          uint8_t isCalled = 0;

          const uint8_t *instr2 = bytecode + CMN_BYTECODE_HEADER_SIZE;

          while (*instr2 != CMN_OPCODE_END)
          {
            // if something jumps into the function (with call or goto)
            if (instr2[0] == CMN_OPCODE_CAL || instr2[0] == CMN_OPCODE_JMA)
            {
              uint32_t c = CMN_instrGetConst(instr2);

              if (c >= addr + 2 && c < addr + funcLen)
              {
                isCalled = 1;
                break;
              }
            }

            instr2 += 2;
          }

          if (!isCalled)
          {
            CMN_bytecodeRemoveInstrs(bytecode,addr,funcLen);
            instr -= 2;
            addr--;

            // remove the function from compiler's symbol table

            if (compiler != 0)
            {
              uint16_t fi = 0;

              for (uint16_t i = 0; i < compiler->symbolCount; ++i)
                if (compiler->symbolTable[i * CMN_STRING_PSEUDOHASH_SIZE] == 'f')
                {
                  if (fi == funcIndex)
                  {
                    compiler->symbolTable[i * CMN_STRING_PSEUDOHASH_SIZE] = 'n';
                    break;
                  }

                  fi++;
                }
            }
          }
          else
            funcIndex++;
        }

        instr += 2;
        addr++;
      }
    }
  }
#undef _ITERATIONS
}

void CMN_preprocessorInit(CMN_Preprocessor *preprocessor, uint8_t minify,
   void (*outFunction)(char))
{
  preprocessor->state = _CMN_PREPPROCESSOR_IN;
  preprocessor->minify = minify;
  preprocessor->outFunction = outFunction;
  CMN_tokenizerInit(&preprocessor->tokenizer);
}

void _CMN_preprocessorOutputChar(void (*outFunc)(char), char c)
{
  if (c >= ' ' && c != '"' && c != '[' && c != ']' && c != '#')
  {
    outFunc('"'); outFunc(c); outFunc('"');
  }
  else
  { // output chars that can't be inside str. lit. as num. lit.
    outFunc('0' + c / 100);
    outFunc('0' + (c / 10) % 10);
    outFunc('0' + c% 10);
  }
}

uint8_t CMN_preprocessorFeedChar(CMN_Preprocessor *preprocessor, char c)
{
  uint8_t separate = 0; // 0: no, 1: space, 2: newline

#define _PCH(c) preprocessor->outFunction(c);

  if (preprocessor->state == _CMN_PREPPROCESSOR_IN)
  {
    if (c == ']')
    {
      preprocessor->state = _CMN_PREPPROCESSOR_OUT;
      _PCH('\n') _PCH('#') _PCH(')') _PCH('\n')
      separate = 1;
    }
    else if (c == '[')
      preprocessor->state = CMN_PREPROCESSOR_ERROR;
    else
      preprocessor->outFunction(c);
  }
  else if (preprocessor->state == _CMN_PREPPROCESSOR_OUT)
  {
    if (c == '[' || c == 0)
    {
      preprocessor->state = _CMN_PREPPROCESSOR_IN;
      _PCH('\n') _PCH('#') _PCH('(') _PCH('\n')
      separate = 1;
    }
    else if (c == ']')
      preprocessor->state = CMN_PREPROCESSOR_ERROR;
    else if (!preprocessor->minify)
    {
      _CMN_preprocessorOutputChar(preprocessor->outFunction,c);
      _PCH(' ')
      _PCH('-') _PCH('>')
      _PCH('\n')
    }
    else
      switch (CMN_tokenizerFeedChar(&(preprocessor->tokenizer),c))
      {
        case CMN_TOKENIZER_TOKEN:
        {
          const char *tokenC = preprocessor->tokenizer.tokenString;
            
          _PCH(' ')

          while (*tokenC != 0)
          {
            _PCH(' ')
            _CMN_preprocessorOutputChar(preprocessor->outFunction,*tokenC);
            _PCH(' ') _PCH('-') _PCH('>')

            tokenC++;
          }

          separate = 2;
          break;
        }

        case CMN_TOKENIZER_ERROR: 
          preprocessor->state = CMN_PREPROCESSOR_ERROR;
          break; 

        default: break;
      }
  }

  if (separate)
  {
    _PCH(' ')
    _PCH(separate == 1 ? '3' : '1')
    _PCH(separate == 1 ? '2' : '0')
    _PCH(' ') _PCH('-') _PCH('>') _PCH('\n')
  }

#undef _PCH

  return preprocessor->state;
}

int CMN_interpretStr(const char *source, uint8_t *memory,
  uint32_t memorySize, uint16_t minCells, uint32_t maxSymbols,
  uint32_t maxSteps, CMN_IOFunction ioFunction,
  void (*statusCallback)(uint8_t, uint32_t, CMN_Interpreter *))
{
  CMN_Compiler compiler;
  CMN_Interpreter interpreter;

  maxSymbols *= CMN_STRING_PSEUDOHASH_SIZE;

  if (maxSymbols > memorySize)
  {
    if (statusCallback)
      statusCallback(1,0,0);

    return 0;
  }

  CMN_compilerInit(&compiler,memory,memorySize - maxSymbols,
    (char *) (memory + memorySize - maxSymbols),maxSymbols,0);

  uint32_t strPos = 0;

  while (1) // compile
  {
    if (CMN_compilerFeedChar(&compiler,source[strPos]) != CMN_COMPILER_OK)
    {
      if (statusCallback)
        statusCallback(1,strPos,0);

      return 0;
    }

    if (source[strPos] == 0)
      break;

    strPos++;
  }

  CMN_bytecodeOptimize(memory,CMN_OPTIMIZE_ALL,0);

  uint8_t *ramStart = memory + CMN_BYTECODE_HEADER_SIZE;

  while (*ramStart != CMN_OPCODE_END)
    ramStart += 2;

  ramStart += 2;

  CMN_interpreterInit(&interpreter,memory,ramStart,
    memory + memorySize - ramStart,minCells,ioFunction,0,0,0);
 
  // run: 
  uint8_t status = CMN_interpreterStep(&interpreter,maxSteps);

  if (status != CMN_INTERPRETER_END)
  {
    if (statusCallback != 0)
      statusCallback(2,0,&interpreter);

    return 0;
  }

  if (statusCallback != 0)
    statusCallback(0,0,&interpreter);

  return interpreter.memory0 != 0 ?
    interpreter.memory0[interpreter.pointers[0][0]] : 0;
}

uint8_t CMN_bytecodeCheckSanity(const uint8_t *bytecode, uint32_t maxSize)
{
  if (maxSize <= CMN_BYTECODE_HEADER_SIZE)
    return CMN_BYTECODE_SANITY_ERROR; // too small, no space for END

  if (bytecode[0] != 'C' || bytecode[1] != 'B')
    return CMN_BYTECODE_SANITY_ERROR_HEADER;
  
  const uint8_t *stopper = bytecode + maxSize;

  const uint8_t *bytecodeOld = bytecode;      
  bytecode += CMN_BYTECODE_HEADER_SIZE;

  char instrStr[16];

  while (*bytecode != CMN_OPCODE_END)
  {
    CMN_instrToStr(bytecode,instrStr);

    if (instrStr[0] == ' ') // no name => unknown opcode
      return CMN_BYTECODE_SANITY_ERROR_INSTR;

    bytecode += 2;

    if (bytecode >= stopper)
      return CMN_BYTECODE_SANITY_ERROR_NO_END;
  }

  if (bytecodeOld[CMN_BYTECODE_CHECKSUM_BYTE] !=
    CMN_bytecodeChecksum(bytecodeOld))
    return CMN_BYTECODE_SANITY_ERROR_CHECKSUM;

  return CMN_BYTECODE_SANITY_OK;
}

#endif // guard