commit 743e16de217c5a621c6c76e89175edeb09797da1
parent d5f06434148bdd7f2d230626ab96c5947a79c41a
Author: William Casarin <jb55@jb55.com>
Date: Wed, 25 Oct 2017 19:15:00 -0700
progress: lots of it
Diffstat:
| M | Makefile | | | 2 | +- |
| M | main.c | | | 4 | ++-- |
| M | misc.h | | | 15 | +++++++++++++-- |
| M | op.c | | | 13 | +++++++++++++ |
| M | op.h | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | parser.y | | | 2 | +- |
| M | script.c | | | 246 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------- |
| M | script.h | | | 4 | +++- |
| M | stack.c | | | 31 | ++++++++++++++++++++++++++++--- |
| M | stack.h | | | 43 | ++++++++++++++++++++++++++++++++----------- |
10 files changed, 370 insertions(+), 41 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,5 +1,5 @@
-CFLAGS=-O2 -Wall -Wno-unused-variable
+CFLAGS=-O0 -g -Wall -Wno-unused-variable
FORBIN=script.o \
parser.tab.o \
diff --git a/main.c b/main.c
@@ -24,9 +24,9 @@ int main() {
script_eval(&reader_stack, &tmp_stack);
printf("script: ");
- script_print(&reader_stack);
+ script_print_ops(&reader_stack);
printf("stack: ");
- script_print(&tmp_stack);
+ script_print_vals(&tmp_stack);
stack_free(&reader_stack);
stack_free(&tmp_stack);
diff --git a/misc.h b/misc.h
@@ -4,7 +4,18 @@
#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
-typedef unsigned char u8;
-typedef unsigned int u32;
+#include <stdint.h>
+
+#define DEBUG 0
+
+/* #define debug(fmt, ...) \ */
+/* do { if (DEBUG) fprintf(stderr, fmt, __VA_ARGS__); } while (0) */
+
+typedef unsigned char u8;
+typedef unsigned short u16;
+typedef unsigned int u32;
+typedef int64_t s64;
+
+#define STATIC_ASSERT(COND,MSG) typedef char static_assertion_##MSG[(!!(COND))*2-1]
#endif /* BCS_MISC_H */
diff --git a/op.c b/op.c
@@ -349,3 +349,16 @@ op_tokenize(char *str) {
}
+void
+val_print(struct val val) {
+ printf("%d", val.val);
+}
+
+const char *
+val_name(struct val val) {
+ switch(val.type) {
+ case VT_INT: return val.is_big? "bi" : "ci"; break;
+ case VT_DATA: return val.is_big? "bd" : "cd"; break;
+ }
+ return "UNK_VAL";
+}
diff --git a/op.h b/op.h
@@ -2,6 +2,10 @@
#ifndef BCS_OP_H
#define BCS_OP_H
+#include "misc.h"
+#include "stack.h"
+#include <stdio.h>
+#include <math.h>
enum opcode
{
@@ -296,11 +300,58 @@ enum opcode_token
_OP_INVALIDOPCODE,
};
+enum valtype {
+ VT_INT=0,
+ VT_DATA, // this could be an overflowed int
+ VT_N
+};
+// UPDATE VAL_TYPE_BITS if you need more valtypes
+
+
+static const int VAL_TYPE_BITS = 1;
+static const int COMPACT_VAL_BITS = (32-VAL_TYPE_BITS-1);
+
+struct val {
+ u8 is_big : 1;
+ u8 type : VAL_TYPE_BITS;
+ u32 val : COMPACT_VAL_BITS;
+};
+
+STATIC_ASSERT(sizeof(struct val) <= 4, stack_op_doesnt_fit_in_stack);
+
// Maximum value that an opcode can be
static const unsigned int MAX_OPCODE = OP_NOP10;
void op_add(enum opcode);
const char * op_name(enum opcode);
enum opcode op_tokenize(char *);
+void val_print(struct val);
+const char * val_name(struct val);
+
+static inline void
+stack_push_val(struct stack *stack, struct val val) {
+#if DEBUG
+ printf("pushing val ");
+ val_print(val);
+ printf("\n");
+#endif
+ void *tmp = 0;
+ stack_push_small(stack, &val, sizeof(struct val));
+}
+
+static inline struct val
+stack_top_val(struct stack *stack, int ind) {
+ struct val val;
+ void *p = stack_top(stack, ind);
+ memcpy(&val, &p, sizeof(struct val));
+ return val;
+}
+
+static inline void
+stack_set_val(struct stack *stack, int ind, struct val val) {
+ struct val *pval = (struct val *)(stack->top + ind);
+ *pval = val;
+}
+
#endif /* BCS_OP_H */
diff --git a/parser.y b/parser.y
@@ -30,7 +30,7 @@ script:
;
line: T_NEWLINE
- | T_OP { stack_push(&reader_stack, $1); }
+ | T_OP { stack_push_small(&reader_stack, &$1, 4); }
| T_EXAMPLE { ; }
diff --git a/script.c b/script.c
@@ -4,27 +4,64 @@
#include "stack.h"
#include <stdio.h>
+static int stack_end(struct stack *stack) {
+ return stack_size(stack);
+}
+
void script_add_error(const char *serror) {
// TODO: set_error
printf("error: %s\n", serror);
}
-u8
+struct val
script_num(int n) {
- // TODO: scriptnum
- /* assert(!"Implement script_num"); */
- return (u8)n;
+ // TODO: scriptnum arithmetic
+ struct val val;
+ val.type = VT_INT;
+ val.is_big = n > (2^COMPACT_VAL_BITS)-1;
+
+ if (!val.is_big) {
+ val.val = n;
+ return val;
+ }
+ else {
+ // looks like we have an int bigger than COMPACT_VAL_BITS in size,
+ // we'll need to store it in a buffer somewhere
+ assert(!"Implement script_num");
+ }
}
+int
+cast_to_bool(struct val val) {
+ // TODO: implement cast_to_bool
+ assert(!"Implement cast_to_bool");
+ /* for (unsigned int i = 0; i < vch.size(); i++) */
+ /* { */
+ /* if (vch[i] != 0) */
+ /* { */
+ /* // Can be negative zero */
+ /* if (i == vch.size()-1 && vch[i] == 0x80) */
+ /* return false; */
+ /* return true; */
+ /* } */
+ /* } */
+ /* return false; */
+}
+
void
script_eval(struct stack *script, struct stack *stack) {
int op_count = 0;
- u8 *p = script->bottom;
- struct stack tmpstack;
+ void **p = script->bottom;
+ struct val val;
+ struct stack _altstack;
+ struct stack *altstack = &_altstack;
+ u8 tmpbuf[32];
+ stack_init(altstack);
while (p < script->top) {
- u8 opcode = *p++;
+ enum opcode opcode = *(enum opcode*)p;
+ p++;
// TODO: pushdata ops
assert(!(opcode >= OP_PUSHDATA1 && opcode <= OP_PUSHDATA4));
@@ -70,41 +107,210 @@ script_eval(struct stack *script, struct stack *stack) {
case OP_15:
case OP_16:
{
- u8 sn = script_num((int)opcode - (int)(OP_1 - 1));
- stack_push(stack, sn);
+ struct val sn = script_num((int)opcode - (int)(OP_1 - 1));
+ stack_push_val(stack, sn);
}
break;
case OP_NOP: break;
+ case OP_INVALIDOPCODE:
+ {
+ return script_add_error("SCRIPT_ERR_INVALID_OPCODE");
+ }
+ break;
+
+ case OP_FROMALTSTACK:
+ {
+ if (stack_size(altstack) < 1)
+ return script_add_error("SCRIPT_ERR_INVALID_ALTSTACK_OPERATION");
+ stack_push(stack, stack_top(altstack, -1));
+ stack_pop(altstack);
+ }
+ break;
+
+ case OP_2DROP:
+ {
+ // (x1 x2 -- )
+ if (stack_size(stack) < 2)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ stack_pop(stack);
+ stack_pop(stack);
+ }
+ break;
case OP_2DUP:
{
- // (x1 x2 -- x1 x2 x1 x2)
- if (stack_size(stack) < 2)
- return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
- u8 v1 = stack_top(stack, -2);
- u8 v2 = stack_top(stack, -1);
- stack_push(stack, v1);
- stack_push(stack, v2);
+ // (x1 x2 -- x1 x2 x1 x2)
+ if (stack_size(stack) < 2)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val v1 = stack_top_val(stack, -2);
+ struct val v2 = stack_top_val(stack, -1);
+ stack_push_val(stack, v1);
+ stack_push_val(stack, v2);
+ }
+ break;
+
+ case OP_3DUP:
+ {
+ // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)
+ if (stack_size(stack) < 3)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val v1 = stack_top_val(stack, -3);
+ struct val v2 = stack_top_val(stack, -2);
+ struct val v3 = stack_top_val(stack, -1);
+ stack_push_val(stack, v1);
+ stack_push_val(stack, v2);
+ stack_push_val(stack, v3);
+ }
+ break;
+
+ case OP_2OVER:
+ {
+ // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
+ if (stack_size(stack) < 4)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val v1 = stack_top_val(stack, -4);
+ struct val v2 = stack_top_val(stack, -3);
+ stack_push_val(stack, v1);
+ stack_push_val(stack, v2);
+ }
+ break;
+
+ case OP_2ROT:
+ {
+ // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
+ if (stack_size(stack) < 6)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val t6 = stack_top_val(stack, -6);
+ struct val t5 = stack_top_val(stack, -5);
+ *(stack->top - 6) = *(stack->top - 4);
+ *(stack->top - 5) = *(stack->top - 3);
+ *(stack->top - 4) = *(stack->top - 2);
+ *(stack->top - 3) = *(stack->top - 1);
+ stack_set_val(stack, -2, t6);
+ stack_set_val(stack, -1, t5);
+ }
+ break;
+
+ case OP_2SWAP:
+ {
+ // (x1 x2 x3 x4 -- x3 x4 x1 x2)
+ if (stack_size(stack) < 4)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+
+ struct val t4 = stack_top_val(stack, -4);
+ struct val t3 = stack_top_val(stack, -3);
+
+ *(stack->top - 4) = *(stack->top - 2);
+ *(stack->top - 3) = *(stack->top - 1);
+ stack_set_val(stack, -2, t4);
+ stack_set_val(stack, -1, t3);
+ }
+ break;
+
+ case OP_IFDUP:
+ {
+ // (x - 0 | x x)
+ if (stack_size(stack) < 1)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val val = stack_top_val(stack, -1);
+ if (cast_to_bool(val))
+ stack_push_val(stack, val);
+ }
+ break;
+
+ case OP_DEPTH:
+ {
+ // -- stacksize
+ struct val sn = script_num(stack_size(stack));
+ stack_push_val(stack, sn);
}
break;
+
+ case OP_DROP:
+ {
+ // (x -- )
+ if (stack_size(stack) < 1)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ stack_pop(stack);
+ }
+ break;
+
+ case OP_DUP:
+ {
+ // (x -- x x)
+ if (stack_size(stack) < 1)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val val = stack_top_val(stack, (-1));
+ stack_push_val(stack, val);
+ }
+ break;
+
+ case OP_NIP:
+ {
+ // (x1 x2 -- x2)
+ if (stack_size(stack) < 2)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ // TODO: sanity check - stack_size() == stack_end(stack)
+ stack_erase(stack, stack_size(stack) - 2);
+ }
+ break;
+
+ case OP_OVER:
+ {
+ // (x1 x2 -- x1 x2 x1)
+ if (stack_size(stack) < 2)
+ return script_add_error("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val val = stack_top_val(stack, (-2));
+ stack_push_val(stack, val);
+ }
+ break;
+
+ default: {
+ sprintf((char*)tmpbuf, "unhandled opcode %s", op_name(opcode));
+ return script_add_error((char*)tmpbuf);
+ }
+
}
}
}
-void script_print(struct stack *stack) {
- u8 *p = stack->bottom;
- while (p < stack->top)
- printf("%s ", op_name(*p++));
+void script_print_ops(struct stack *stack) {
+ void **p = stack->bottom;
+ while (p < stack->top) {
+ enum opcode opcode = (enum opcode)*p++;
+ printf("%s ", op_name(opcode));
+ }
printf("\n");
}
+void script_print_vals(struct stack *stack) {
+ void **p = stack->bottom;
+ while (p < stack->top) {
+ struct val val;
+ memcpy(&val, &*p++, sizeof(struct val));
+ val_print(val);
+ putchar(' ');
+ }
+ putchar('\n');
+}
+
int script_init(struct script *script) {
+ stack_init(&script->pushdata);
return stack_init(&script->data);
}
void script_free(struct script *script) {
stack_free(&script->data);
+ void **p = script->pushdata.bottom;
+ assert(p);
+ while (p < script->pushdata.top) {
+ assert(*p);
+ p++;
+ }
+}
+
+int script_new(struct script *script) {
}
diff --git a/script.h b/script.h
@@ -22,12 +22,14 @@ static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20
struct script {
struct stack data;
+ struct stack pushdata; // a stack of pushdata stacks
};
int script_new(struct script *);
void script_free(struct script *);
void script_eval(struct stack *, struct stack*);
-void script_print(struct stack *);
+void script_print_ops(struct stack *);
+void script_print_vals(struct stack *);
#endif /* BTCS_SCRIPT_H */
diff --git a/stack.c b/stack.c
@@ -1,6 +1,7 @@
#include "stack.h"
#include <stdlib.h>
+#include <stdio.h>
#include <string.h>
void
@@ -11,7 +12,7 @@ stack_clear(struct stack *stack) {
int
stack_init_size(struct stack *stack, int capacity) {
if (capacity > DEFAULT_STACK_SIZE) {
- u8 *bottom = (u8*)malloc(capacity);
+ void *bottom = malloc(capacity * sizeof(void*));
if (!bottom) return 0;
stack->bottom = bottom;
stack->top = bottom;
@@ -45,11 +46,35 @@ stack_expand(struct stack *stack) {
}
void
-stack_push(struct stack *stack, u8 byte) {
+stack_push(struct stack *stack, void *val) {
+ #if DEBUG
+ printf("pushing: %d %p\n", stack_size(stack), val);
+ #endif
+
if ((stack_size(stack) + 1) > stack->capacity) {
stack_expand(stack);
}
- *stack->top++ = byte;
+ *stack->top++ = val;
+}
+
+// TODO: UNTESTED!
+void *
+stack_erase(struct stack *stack, int ind) {
+ int size = stack_size(stack);
+ assert(ind >= 0);
+ assert(ind < size);
+ void * erased = *(stack->bottom + ind);
+ memcpy(stack->bottom + ind, stack->bottom + ind + size, size);
+ stack->top--;
+ return erased;
+}
+
+void *
+stack_pop(struct stack *stack) {
+ assert(stack_size(stack) != 0);
+ void * v = stack_top(stack, -1);
+ stack->top--;
+ return v;
}
diff --git a/stack.h b/stack.h
@@ -3,31 +3,36 @@
#define BTCS_STACK_H
#include <assert.h>
+#include <string.h>
+#include <stdio.h>
#include "misc.h"
// Maximum number of values on script interpreter stack
static const int MAX_STACK_SIZE = 1000;
// Maximum number of values on script interpreter stack
-static const int DEFAULT_STACK_SIZE = 64;
+static const int DEFAULT_STACK_SIZE = 100;
struct stack {
- u8 _data[DEFAULT_STACK_SIZE];
- u8 * bottom;
- u8 * top;
+ void *_data[DEFAULT_STACK_SIZE];
+ void **bottom;
+ void **top;
int capacity;
};
-int stack_init(struct stack *);
-int stack_init_size(struct stack *, int size);
-void stack_free(struct stack *);
-void stack_clear(struct stack *);
-void stack_push(struct stack *, u8 val);
+int stack_init(struct stack *);
+int stack_init_size(struct stack *, int size);
+void stack_free(struct stack *);
+void stack_clear(struct stack *);
+void* stack_pop(struct stack *);
+void* stack_erase(struct stack *, int ind);
+void stack_push(struct stack *, void *val);
-static inline u8
+static inline void *
stack_top(struct stack *stack, int ind) {
- u8 *p = stack->top + ind;
+ void **p = stack->top + ind;
assert(p >= stack->bottom);
+ assert(p);
return *p;
}
@@ -36,4 +41,20 @@ stack_size(struct stack *stack) {
return stack->top - stack->bottom;
}
+static inline void
+stack_push_small(struct stack *stack, void *p, size_t size) {
+#if DEBUG
+ u8 *b = (u8*)p;
+ printf("pushing small", "");
+ for (size_t i = 0; i < size; ++i) {
+ printf(" %02x", b[i]);
+ }
+ printf("\n");
+#endif
+ assert(size <= sizeof(void*));
+ void *tmp = 0;
+ memcpy(&tmp, p, size);
+ stack_push(stack, tmp);
+}
+
#endif /* BTCS_STACK_H */
