commit c50cf5a2b2be76ec5c4a0f4098eef0dc87904684
parent daba4328d4644b1aeb018957ef5326181e8971b0
Author: William Casarin <jb55@jb55.com>
Date: Mon, 30 Oct 2017 22:39:43 -0700
variable sized stack elements
Diffstat:
| M | Makefile | | | 3 | +++ |
| A | alloc.c | | | 87 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | alloc.h | | | 32 | ++++++++++++++++++++++++++++++++ |
| A | consts.h | | | 22 | ++++++++++++++++++++++ |
| M | main.c | | | 3 | +++ |
| M | misc.h | | | 6 | ++++++ |
| M | op.c | | | 17 | ++++++++++++++--- |
| M | op.h | | | 37 | +------------------------------------ |
| M | script.c | | | 300 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------- |
| M | script.h | | | 16 | ---------------- |
| A | script_num.c | | | 86 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | script_num.h | | | 53 | +++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | stack.c | | | 1 | + |
| M | stack.h | | | 42 | ++++++++++++++++++++++++------------------ |
| M | test.c | | | 35 | ++++++++++++++++++++++++++++++++++- |
| A | val.c | | | 71 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | val.h | | | 48 | ++++++++++++++++++++++++++++++++++++++++++++++++ |
17 files changed, 747 insertions(+), 112 deletions(-)
diff --git a/Makefile b/Makefile
@@ -4,6 +4,9 @@ CFLAGS=-O0 -Ideps -std=c99 -g -Wall -Wno-unused-variable -Wno-unused-function
DEPS=script.c \
oplookup.c \
op.c \
+ val.c \
+ alloc.c \
+ script_num.c \
stack.c
CLIDEPS=parser.tab.c \
diff --git a/alloc.c b/alloc.c
@@ -0,0 +1,87 @@
+
+
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "alloc.h"
+#include "stack.h"
+
+static struct arenas g_arenas;
+
+void
+alloc_arenas() {
+ alloc_arena_sizes(0, MAX_STACK_SIZE, MAX_STACK_SIZE * MAX_STACK_SIZE);
+}
+
+void
+alloc_arena_sizes(struct arenas *arenas, const int nums, const int bytes) {
+ if (!arenas) arenas = &g_arenas;
+ arenas->nums = (struct num*)calloc(nums, sizeof(struct num));
+ assert(arenas->nums);
+ arenas->bytes = (char*)calloc(bytes, 1);
+ stack_init_size(&arenas->bytes_map, bytes);
+ arenas->bytes_top = arenas->bytes;
+ arenas->nbytes = bytes;
+}
+
+struct num *
+num_pool_get(const int ind) {
+ return &g_arenas.nums[ind];
+}
+
+
+struct num *
+num_pool_new(int *ind) {
+ *ind = g_arenas.num_count++;
+ struct num *p;
+ p = &g_arenas.nums[*ind];
+ assert(p);
+ assert(p->val == 0 && p->ind == 0);
+ return p;
+}
+
+char *
+byte_pool_new(const char *bytes, const u16 len) {
+ assert(g_arenas.bytes_top - g_arenas.bytes + len <= g_arenas.nbytes);
+ char *start = g_arenas.bytes_top;
+ u16 *c = (u16*)g_arenas.bytes_top;
+ *c++ = len;
+ char *p = (char*)c;
+ memcpy(p, bytes, len);
+ p += len;
+ g_arenas.bytes_top = p;
+ assert(*p == 0);
+ return start;
+}
+
+
+// useful for quick alloc/deallocs
+char *
+byte_pool_pop() {
+ char *p = (char*)stack_pop(&g_arenas.bytes_map);
+ u16 *c = (u16*)p;
+ memset(p, 0, *c + sizeof(u16));
+ return p;
+}
+
+
+char *
+byte_pool_get(const int ind, u16 *len) {
+ char *p;
+ u16 *up;
+ p = (char*)(g_arenas.bytes_map.bottom + ind);
+ assert(p);
+ up = (u16*)p;
+ *len = *(up++);
+ p = (char*)up;
+ return p;
+}
+
+void
+free_arenas(struct arenas *arenas) {
+ if (!arenas) arenas = &g_arenas;
+ if (!arenas) return;
+ stack_free(&arenas->bytes_map);
+ free(arenas->bytes);
+ free(arenas->nums);
+}
diff --git a/alloc.h b/alloc.h
@@ -0,0 +1,32 @@
+
+#ifndef BTCS_ALLOC_H
+#define BTCS_ALLOC_H
+
+#include "consts.h"
+#include "script_num.h"
+
+// MAX_OPS_PER_SCRIPT *
+#define MAX_PUSHDATA_REFS (MAX_OPS_PER_SCRIPT * MAX_STACK_SIZE)
+#define ALLOC_PUSHDATA_BYTES (MAX_STACK_SIZE * MAX_OPS_PER_SCRIPT)
+
+struct num * num_pool_new(int *ind);
+struct num * num_pool_get(const int ind);
+
+char * byte_pool_new(const char *bytes, const u16 len);
+char * byte_pool_get(const int ind, u16 *len);
+char * byte_pool_pop();
+
+struct arenas {
+ struct num *nums;
+ char *bytes;
+ char *bytes_top;
+ struct stack bytes_map;
+ int nbytes;
+ int num_count;
+};
+
+void alloc_arena_sizes(struct arenas *, const int nums, const int bytes);
+void alloc_arenas();
+void free_arenas(struct arenas *arenas);
+
+#endif /* BTCS_ALLOC_H */
diff --git a/consts.h b/consts.h
@@ -0,0 +1,22 @@
+
+#ifndef BTCS_CONSTS_H
+#define BTCS_CONSTS_H
+
+// Maximum number of bytes pushable to the stack
+static const unsigned int MAX_SCRIPT_ELEMENT_SIZE = 520;
+
+// Maximum number of non-push operations per script
+static const int MAX_OPS_PER_SCRIPT = 201;
+
+// Maximum number of public keys per multisig
+static const int MAX_PUBKEYS_PER_MULTISIG = 20;
+
+// Maximum script length in bytes
+static const int MAX_SCRIPT_SIZE = 10000;
+
+// Threshold for nLockTime: below this value it is interpreted as block number,
+// otherwise as UNIX timestamp.
+static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
+
+
+#endif /* BTCS_CONSTS_H */
diff --git a/main.c b/main.c
@@ -3,6 +3,7 @@
#include <stdlib.h>
#include "stack.h"
#include "script.h"
+#include "alloc.h"
extern int yyparse();
extern FILE* yyin;
@@ -15,6 +16,7 @@ int main() {
yyin = stdin;
struct stack tmp_stack;
+ alloc_arenas(0, MAX_STACK_SIZE, MAX_STACK_SIZE * MAX_STACK_SIZE);
stack_init(&reader_stack);
stack_init(&tmp_stack);
@@ -30,6 +32,7 @@ int main() {
stack_free(&reader_stack);
stack_free(&tmp_stack);
+ free_arenas(0);
return 0;
}
diff --git a/misc.h b/misc.h
@@ -8,6 +8,12 @@
#define DEBUG 0
+enum compiler_options {
+ CO_WARNINGS_ARE_ERRORS = 1 << 1,
+ CO_WARN_MINIMAL = 1 << 2
+};
+
+
/* #define debug(fmt, ...) \ */
/* do { if (DEBUG) fprintf(stderr, fmt, __VA_ARGS__); } while (0) */
diff --git a/op.c b/op.c
@@ -2,6 +2,7 @@
#include "script.h"
#include "oplookup.h"
#include "op.h"
+#include "alloc.h"
#include "misc.h"
#include <stdio.h>
@@ -353,14 +354,24 @@ op_tokenize(char *str) {
void
val_print(struct val val) {
- printf("%d", val.val);
+ struct num *n;
+ switch(val.type) {
+ case VT_SCRIPTNUM:
+ assert(val.ind != -1);
+ n = num_pool_get(val.ind);
+ printf("%lu", n->val);
+ break;
+ default:
+ assert(!"val_print data");
+ }
}
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;
+ case VT_SCRIPTNUM: return "n"; break;
+ case VT_SMALLINT: return "s"; break;
+ case VT_DATA: return "d"; break;
}
return "UNK_VAL";
}
diff --git a/op.h b/op.h
@@ -4,6 +4,7 @@
#include "misc.h"
#include "stack.h"
+#include "val.h"
#include <stdio.h>
#include <math.h>
@@ -300,26 +301,6 @@ 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
-
-
-#define VAL_TYPE_BITS 1
-/* static const int COMPACT_VAL_BITS = (32-VAL_TYPE_BITS-1); */
-#define COMPACT_VAL_BITS 30
-
-struct val {
- u8 is_big : 1;
- u8 type : VAL_TYPE_BITS;
- u32 val : COMPACT_VAL_BITS;
-};
-
-STATIC_ASSERT(sizeof(struct val) <= 4, val_doesnt_fit_in_stack);
-
// Maximum value that an opcode can be
static const unsigned int MAX_OPCODE = OP_NOP10;
@@ -329,8 +310,6 @@ enum opcode op_tokenize(char *);
void val_print(struct val);
const char * val_name(struct val);
-#define smallintval(n) ((struct val){ .is_big = 0, .type = VT_INT, .val = n })
-
static inline void
stack_push_val(struct stack *stack, struct val val) {
#if 0
@@ -346,19 +325,5 @@ stack_push_op(struct stack *stack, enum opcode opcode) {
stack_push_small(enum opcode, stack, &opcode);
}
-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/script.c b/script.c
@@ -1,7 +1,9 @@
#include "script.h"
#include "op.h"
+#include "script_num.h"
#include "stack.h"
+#include "alloc.h"
#include <stdio.h>
#define SCRIPTERR(serr) script_add_error(c, opcode, serr)
@@ -17,54 +19,44 @@ void script_add_warning(const char *warning) {
fprintf(stderr, "warning: %s\n", warning);
}
-struct val
-script_num(int 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; */
+ switch (val.type) {
+ case VT_SCRIPTNUM: {
+ struct num *sn = num_pool_get(val.ind);
+ return sn->val != 0;
+ }
+ case VT_DATA: {
+ u16 len;
+ const char * bytes = byte_pool_get(val.ind, &len);
+ return *bytes != 0;
+ }
+ }
+ assert(!"Unhandled val.type in cast_to_bool");
}
int
script_eval(struct stack *script, struct stack *stack) {
int op_count = 0;
void **p = script->bottom;
+ static const struct val val_true = {.type = VT_SMALLINT, .ind = 1};
+ static const struct val val_false = {.type = VT_SMALLINT, .ind = 0};
+ static const struct num bn_one = {.val = 1, .ind = -1};
+ static const struct num bn_zero = {.val = 0, .ind = -1};
struct val val;
struct stack _altstack;
struct stack _ifstack;
struct stack *altstack = &_altstack;
struct stack *ifstack = &_ifstack;
- int flags = 0;
+ int flags = CO_WARNINGS_ARE_ERRORS | CO_WARN_MINIMAL;
int c = 0;
- u8 tmpbuf[32];
+ // TODO: require minimal?
+ int require_minimal =
+ !(flags & ~(CO_WARNINGS_ARE_ERRORS | CO_WARN_MINIMAL));
+
+ char tmpbuf[32];
stack_init(altstack);
stack_init(ifstack);
@@ -76,6 +68,7 @@ script_eval(struct stack *script, struct stack *stack) {
// TODO: pushdata ops
assert(!(opcode >= OP_PUSHDATA1 && opcode <= OP_PUSHDATA4));
+ // Note OP_RESERVED does not count towards the opcode limit.
if (opcode > OP_16 && ++op_count > MAX_OPS_PER_SCRIPT)
SCRIPTERR("MAX_OPS_PER_SCRIPT");
@@ -118,8 +111,10 @@ script_eval(struct stack *script, struct stack *stack) {
case OP_15:
case OP_16:
{
- struct val sn = script_num((int)opcode - (int)(OP_1 - 1));
- stack_push_val(stack, sn);
+ struct num sn;
+ sn_from_int((int)opcode - (int)(OP_1 - 1), &sn);
+ struct val val = sn_to_val(&sn);
+ stack_push_val(stack, val);
}
break;
@@ -268,8 +263,10 @@ script_eval(struct stack *script, struct stack *stack) {
case OP_DEPTH:
{
// -- stacksize
- struct val sn = script_num(stack_size(stack));
- stack_push_val(stack, sn);
+ struct num sn;
+ sn_from_int(stack_size(stack), &sn);
+ struct val val = sn_to_val(&sn);
+ stack_push_val(stack, val);
}
break;
@@ -313,9 +310,236 @@ script_eval(struct stack *script, struct stack *stack) {
}
break;
+
+ case OP_PICK:
+ case OP_ROLL:
+ {
+ // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
+ // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
+ if (stack_size(stack) < 2)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct num *n;
+
+ enum sn_result res =
+ sn_from_val(stack_top_val(stack, -1), &n, require_minimal);
+
+ if (res != SN_SUCCESS) {
+ sprintf(tmpbuf, "invalid scriptnum %d", res);
+ SCRIPTERR(tmpbuf);
+ }
+
+ stack_pop(stack);
+ if (n->val < 0 || n->val >= (int)stack_size(stack))
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val val = stack_top_val(stack, (-(n->val))-1);
+ if (opcode == OP_ROLL)
+ assert(!"Finish OP_ROLL");
+ /* stack.erase(stack.end()-n-1); */
+ stack_push_val(stack, val);
+ }
+ break;
+
+ case OP_ROT:
+ {
+ // (x1 x2 x3 -- x2 x3 x1)
+ // x2 x1 x3 after first swap
+ // x2 x3 x1 after second swap
+ if (stack_size(stack) < 3)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ stack_swap(stack, -3, -2);
+ stack_swap(stack, -2, -1);
+ }
+ break;
+
+ case OP_SWAP:
+ {
+ // (x1 x2 -- x2 x1)
+ if (stack_size(stack) < 2)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ stack_swap(stack, -2, -1);
+ }
+ break;
+
+ case OP_TUCK:
+ {
+ // (x1 x2 -- x2 x1 x2)
+ if (stack_size(stack) < 2)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val val = stack_top_val(stack, -1);
+ stack_swap(stack, -2, -1);
+ stack_push(stack, stack_top(stack, -2));
+ }
+ break;
+
+
+ case OP_SIZE:
+ {
+ // (in -- in size)
+ if (stack_size(stack) < 1)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct num sn;
+ sn_from_int(stack_size(stack) - 1, &sn);
+ struct val val = sn_to_val(&sn);
+ stack_push_val(stack, val);
+ }
+ break;
+
+
+ //
+ // Bitwise logic
+ //
+ case OP_EQUAL:
+ case OP_EQUALVERIFY:
+ //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
+ {
+ // (x1 x2 - bool)
+ if (stack_size(stack) < 2)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct val v1 = stack_top_val(stack, -2);
+ struct val v2 = stack_top_val(stack, -1);
+ int equal = val_eq(v1, v2, require_minimal);
+ // OP_NOTEQUAL is disabled because it would be too easy to say
+ // something like n != 1 and have some wiseguy pass in 1 with extra
+ // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
+ //if (opcode == OP_NOTEQUAL)
+ // fEqual = !fEqual;
+ stack_pop(stack);
+ stack_pop(stack);
+ stack_push_val(stack, equal ? val_true : val_false);
+ if (opcode == OP_EQUALVERIFY)
+ {
+ if (equal)
+ stack_pop(stack);
+ else
+ return SCRIPTERR("SCRIPT_ERR_EQUALVERIFY");
+ }
+ }
+ break;
+
+
+ //
+ // Numeric
+ //
+ case OP_1ADD:
+ case OP_1SUB:
+ case OP_NEGATE:
+ case OP_ABS:
+ case OP_NOT:
+ case OP_0NOTEQUAL:
+ {
+ // (in -- out)
+ if (stack_size(stack) < 1)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct num *bn;
+ enum sn_result res =
+ sn_from_val(stack_top_val(stack, -1), &bn, require_minimal);
+
+ if (res != SN_SUCCESS) {
+ sprintf(tmpbuf, "invalid scriptnum %d", res);
+ SCRIPTERR(tmpbuf);
+ }
+
+ switch (opcode)
+ {
+ case OP_1ADD: bn->val += 1; break;
+ case OP_1SUB: bn->val -= 1; break;
+ case OP_NEGATE: bn->val = -bn->val; break;
+ case OP_ABS:
+ if (bn->val < bn_zero.val)
+ bn->val = -(bn->val);
+ break;
+ case OP_NOT: bn->val = (bn->val == 0); break;
+ case OP_0NOTEQUAL: bn->val = (bn->val != 0); break;
+ default: assert(!"invalid opcode"); break;
+ }
+ stack_pop(stack);
+ stack_push_val(stack, sn_to_val(bn));
+ }
+ break;
+
+ case OP_ADD:
+ case OP_SUB:
+ case OP_BOOLAND:
+ case OP_BOOLOR:
+ case OP_NUMEQUAL:
+ case OP_NUMEQUALVERIFY:
+ case OP_NUMNOTEQUAL:
+ case OP_LESSTHAN:
+ case OP_GREATERTHAN:
+ case OP_LESSTHANOREQUAL:
+ case OP_GREATERTHANOREQUAL:
+ case OP_MIN:
+ case OP_MAX:
+ {
+ // (x1 x2 -- out)
+ if (stack_size(stack) < 2)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct num *bn1, *bn2, bn;
+ sn_from_val(stack_top_val(stack, -2), &bn1, require_minimal);
+ sn_from_val(stack_top_val(stack, -1), &bn2, require_minimal);
+ /* struct num bn(0); */
+ switch (opcode)
+ {
+ case OP_ADD:
+ bn.val = bn1->val + bn2->val;
+ break;
+
+ case OP_SUB:
+ bn.val = bn1->val - bn2->val;
+ break;
+
+ case OP_BOOLAND: bn.val = bn1->val != 0 && bn2->val != 0;
+ break;
+ case OP_BOOLOR: bn.val = bn1->val != 0 || bn2->val != 0;
+ break;
+ case OP_NUMEQUAL: bn.val = bn1->val == bn2->val; break;
+ case OP_NUMEQUALVERIFY: bn.val = bn1->val == bn2->val; break;
+ case OP_NUMNOTEQUAL: bn.val = bn1->val != bn2->val; break;
+ case OP_LESSTHAN: bn.val = bn1->val < bn2->val; break;
+ case OP_GREATERTHAN: bn.val = bn1->val > bn2->val; break;
+ case OP_LESSTHANOREQUAL: bn.val = bn1->val <= bn2->val; break;
+ case OP_GREATERTHANOREQUAL: bn.val = bn1->val >= bn2->val; break;
+ case OP_MIN:
+ bn.val = bn1->val < bn2->val ? bn1->val : bn2->val;
+ break;
+ case OP_MAX:
+ bn.val = bn1->val > bn2->val ? bn1->val : bn2->val;
+ break;
+ default: assert(!"invalid opcode"); break;
+ }
+ stack_pop(stack);
+ stack_pop(stack);
+ stack_push_val(stack, sn_to_val(&bn));
+
+ if (opcode == OP_NUMEQUALVERIFY)
+ {
+ if (cast_to_bool(stack_top_val(stack, -1)))
+ stack_pop(stack);
+ else
+ return SCRIPTERR("SCRIPT_ERR_NUMEQUALVERIFY");
+ }
+ }
+ break;
+
+ case OP_WITHIN:
+ {
+ // (x min max -- out)
+ if (stack_size(stack) < 3)
+ return SCRIPTERR("SCRIPT_ERR_INVALID_STACK_OPERATION");
+ struct num *bn1, *bn2, *bn3;
+ sn_from_val(stack_top_val(stack, -3), &bn1, require_minimal);
+ sn_from_val(stack_top_val(stack, -2), &bn2, require_minimal);
+ sn_from_val(stack_top_val(stack, -1), &bn3, require_minimal);
+ int fval = bn2->val <= bn1->val && bn1->val < bn3->val;
+ stack_pop(stack);
+ stack_pop(stack);
+ stack_pop(stack);
+ stack_push_val(stack, fval ? val_true : val_false);
+ }
+ break;
+
default: {
- sprintf((char*)tmpbuf, "unhandled opcode %s", op_name(opcode));
- return SCRIPTERR((char*)tmpbuf);
+ return SCRIPTERR("unhandled opcode");
}
}
diff --git a/script.h b/script.h
@@ -4,22 +4,6 @@
#include "stack.h"
-// Maximum number of bytes pushable to the stack
-static const unsigned int MAX_SCRIPT_ELEMENT_SIZE = 520;
-
-// Maximum number of non-push operations per script
-static const int MAX_OPS_PER_SCRIPT = 201;
-
-// Maximum number of public keys per multisig
-static const int MAX_PUBKEYS_PER_MULTISIG = 20;
-
-// Maximum script length in bytes
-static const int MAX_SCRIPT_SIZE = 10000;
-
-// Threshold for nLockTime: below this value it is interpreted as block number,
-// otherwise as UNIX timestamp.
-static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
-
struct script {
struct stack data;
struct stack pushdata; // a stack of pushdata stacks
diff --git a/script_num.c b/script_num.c
@@ -0,0 +1,86 @@
+
+#include "script_num.h"
+#include "alloc.h"
+#include "val.h"
+
+/**
+ * Numeric opcodes (OP_1ADD, etc) are restricted to operating on 4-byte
+ * integers. The semantics are subtle, though: operands must be in the range
+ * [-2^31 +1...2^31 -1], but results may overflow (and are valid as long as they
+ * are not used in a subsequent numeric operation). struct num enforces those
+ * semantics by storing results as an int64 and allowing out-of-range values to
+ * be returned, but throwing an exception if arithmetic is done or the result is
+ * interpreted as an integer.
+ */
+
+
+void
+sn_from_int(int n, struct num *sn) {
+ sn->ind = -1;
+ sn->val = n;
+}
+
+
+/* enum sn_result */
+/* sn_to_int(struct num *sn, int *res) { */
+/* if (sn_overflowed(sn)) { */
+/* return SN_ERR_OVERFLOWED_INT; */
+/* } */
+/* } */
+
+
+const char *
+sn_serialize(struct num *sn, u16 *len) {
+ assert(!"implement sn_serialize");
+ return "";
+}
+
+
+int
+sn_overflowed(struct num *num) {
+ return (num->val & ~0xFFFFFFFF) != 0;
+}
+
+
+// Return a script num only if it's still a 4-byte integer
+enum sn_result
+sn_from_val(struct val val, struct num ** sn, int require_minimal) {
+ switch (val.type) {
+ case VT_SCRIPTNUM:
+ *sn = num_pool_get(val.ind);
+ assert(*sn);
+
+ // we're trying to return a scriptnum that is larger than 4 bytes. This is not
+ // a valid scriptnum at this point. return an error.
+ if (sn_overflowed(*sn)) {
+ *sn = 0;
+ return SN_ERR_OVERFLOWED_INT;
+ }
+
+ break;
+ case VT_DATA:
+ assert(!"TODO implement raw data to script num");
+ }
+
+ return SN_SUCCESS;
+}
+
+struct val
+sn_to_val(struct num *sn) {
+ struct val val;
+ struct num *snref;
+ int ind;
+
+ // TODO: implement return overflowed scriptnums
+ assert(!sn_overflowed(sn));
+
+ val.type = VT_SCRIPTNUM;
+ if (sn->ind > -1)
+ val.ind = sn->ind;
+ else {
+ snref = num_pool_new(&ind);
+ *sn = *snref;
+ val.ind = ind;
+ }
+ return val;
+}
diff --git a/script_num.h b/script_num.h
@@ -0,0 +1,53 @@
+
+#ifndef BTCS_SCRIPTNUM_H
+#define BTCS_SCRIPTNUM_H
+
+#include "misc.h"
+#include "val.h"
+
+enum sn_result {
+ SN_SUCCESS,
+ SN_ERR_OVERFLOWED_INT
+};
+
+struct num {
+ s64 val;
+ int ind;
+};
+
+void
+sn_from_int(int n, struct num *);
+
+int
+sn_overflowed(struct num *num);
+
+enum sn_result
+sn_from_val(struct val val, struct num ** sn, int require_minimal);
+
+struct val
+sn_to_val(struct num *sn);
+
+int
+sn_to_int(struct num *sn, int require_minimal);
+
+const char *
+sn_serialize(struct num *sn, u16 *len);
+
+
+static void inline
+sn_add(struct num *a, struct num *b, struct num *c) {
+ c->val = a->val + b->val;
+}
+
+static void inline
+sn_sub(struct num *a, struct num *b, struct num *c) {
+ c->val = a->val - b->val;
+}
+
+static void inline
+sn_neg(struct num *a, struct num *b) {
+ b->val = -(a->val);
+}
+
+
+#endif /* BTCS_SCRIPTNUM_H */
diff --git a/stack.c b/stack.c
@@ -96,6 +96,7 @@ stack_erase(struct stack *stack, int ind) {
void *
stack_pop(struct stack *stack) {
+ assert(stack);
assert(stack_size(stack) != 0);
void * v = stack_top(stack, -1);
stack->top--;
diff --git a/stack.h b/stack.h
@@ -41,6 +41,13 @@ stack_size(struct stack *stack) {
return stack->top - stack->bottom;
}
+static inline void
+stack_swap(struct stack *stack, int ind1, int ind2) {
+ void *temp = *(stack->top + ind1);
+ *(stack->top + ind1) = *(stack->top + ind2);
+ *(stack->top + ind2) = temp;
+}
+
#define stack_push_small(T, stack, val) { \
assert(sizeof(T) <= sizeof(void*)); \
void *tmp = 0; \
@@ -48,24 +55,23 @@ stack_size(struct stack *stack) {
stack_push(stack, tmp); \
}
-#define stack_top_small(T, stack, ind) { \
- memcpy(val, stack_top(stack, ind)); \
- }
+#define stack_top_small(T, stack, v, ind) \
+ memcpy(v, stack->top + ind, sizeof(T))
-/* static inline void */
-/* _stack_push_smallt(struct stack *stack, void *p, size_t size) { */
-/* #if 0 */
-/* 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); */
-/* } */
+static inline void
+_stack_push_smallt(struct stack *stack, void *p, size_t size) {
+#if 0
+ 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 */
diff --git a/test.c b/test.c
@@ -2,6 +2,7 @@
#include "script.h"
#include "op.h"
+#include "alloc.h"
#include "tap.c/tap.h"
typedef void (program)(struct stack *script, struct stack *stack,\
@@ -18,16 +19,27 @@ typedef void (program)(struct stack *script, struct stack *stack,\
/* stack_push_op(OP_1); */
/* } */
+
static inline void
ok_stacks_equal(struct stack *s1, struct stack *s2, const char *context) {
void **b1 = s1->bottom;
void **b2 = s2->bottom;
+ struct val v1;
+ struct val v2;
size_t s1size = stack_size(s1);
size_t s2size = stack_size(s2);
cmp_ok(s1size, "==", s2size, "%s: expected stack size", context);
- is(memcmp(b1, b2, s1size*sizeof(void*)), 0, "%s: expected stack memory", context);
+
+ for (size_t i = 0; i < s1size; ++i) {
+ v1 = stack_top_val(s1, i);
+ v2 = stack_top_val(s2, i);
+
+ if (!val_eq(v1, v2, 0)) {
+ is(val_name(v1), val_name(v2), "%s: stack vals match", context);
+ }
+ }
}
TEST(test_simple) {
@@ -59,6 +71,23 @@ TEST(test_2dup_not_enough_input) {
}
+// TODO test scriptnum overflows
+// TODO test scriptnum negative zero boolean logic
+// TODO test scriptnum add into overflow + hash
+// TODO test unpooled scriptnum index is == -1 for various constructors
+
+/* TODO test ops:
+ *
+ * OP_1ADD
+ * OP_1SUB
+ * OP_NEGATE
+ * OP_ABS
+ * OP_NOT
+ * OP_0NOTEQUAL
+ *
+ */
+
+
static inline void
run_test(struct stack *script, struct stack *stack, struct stack *expected,
program *prog)
@@ -77,6 +106,8 @@ main(int argc, char *argv[]) {
struct stack *stack = &_stack;
struct stack *expected = &_expected;
+ alloc_arenas();
+
plan(5);
stack_init(script);
@@ -91,6 +122,8 @@ main(int argc, char *argv[]) {
stack_free(stack);
stack_free(script);
+ free_arenas(0);
+
done_testing();
return 0;
}
diff --git a/val.c b/val.c
@@ -0,0 +1,71 @@
+
+#include <assert.h>
+#include "op.h"
+#include "val.h"
+#include "alloc.h"
+#include "script_num.h"
+
+static const char intbytes[] = {
+ OP_1NEGATE,
+ OP_0,
+ OP_1, OP_2, OP_3, OP_4, OP_5,
+ OP_6, OP_7, OP_8, OP_9, OP_10,
+ OP_11, OP_12, OP_13, OP_14, OP_15,
+ OP_16
+};
+
+const char *
+val_serialize(struct val val, u16 *len, int require_minimal) {
+ struct num *sn;
+ int n, ind;
+ switch (val.type) {
+ case VT_SCRIPTNUM:
+ sn = num_pool_get(val.ind);
+ assert(sn);
+ return sn_serialize(sn, len);
+ case VT_DATA:
+ return byte_pool_get(val.ind, len);
+ case VT_SMALLINT:
+ *len = 1;
+ n = val.ind;
+ if (n >= -1 && n <= 16) {
+ val.type = VT_SMALLINT;
+ return &intbytes[n+1];
+ }
+ else {
+ assert(!"non-small VT_SMALLINT");
+ }
+ }
+
+ assert(!"val_serialize missing implementation");
+ return 0;
+}
+
+int
+val_eq(struct val a, struct val b, int require_minimal) {
+ u16 alen, blen;
+ int eq = 0;
+ const char *abytes, *bbytes;
+ abytes = val_serialize(a, &alen, require_minimal);
+ bbytes = val_serialize(b, &blen, require_minimal);
+ // TODO: what if they're semantically equivalent? or does that matter?
+
+ if (alen != blen) {
+ if (a.type == VT_DATA) byte_pool_pop();
+ if (b.type == VT_DATA) byte_pool_pop();
+ return 0;
+ }
+
+ eq = memcmp(abytes, bbytes, alen) == 0;
+
+ if (a.type == VT_DATA) byte_pool_pop();
+ if (b.type == VT_DATA) byte_pool_pop();
+
+ return eq;
+}
+
+
+/* struct val */
+/* val_int(s64 n) { */
+/* struct val val; */
+/* } */
diff --git a/val.h b/val.h
@@ -0,0 +1,48 @@
+
+#ifndef BTCS_VAL_H
+#define BTCS_VAL_H
+
+#include "misc.h"
+#include "stack.h"
+
+enum valtype {
+ VT_SCRIPTNUM=0,
+ VT_SMALLINT,
+ VT_DATA,
+ VT_N
+};
+// UPDATE VAL_TYPE_BITS if you need more valtypes
+
+
+#define VAL_TYPE_BITS 2
+/* static const int COMPACT_VAL_BITS = (32-VAL_TYPE_BITS-1); */
+#define VAL_COMPACT_BITS 30
+
+struct val {
+ u8 type : VAL_TYPE_BITS;
+ int ind : VAL_COMPACT_BITS;
+};
+
+#define smallintval(n) ((struct val){ .type = VT_SMALLINT, .ind = n })
+
+// we want val to fit into the size of a 32-bit pointer
+STATIC_ASSERT(sizeof(struct val) <= 4, val_doesnt_fit_in_stack);
+
+
+static inline struct val
+stack_top_val(struct stack *stack, int ind) {
+ struct val val;
+ stack_top_small(struct val, stack, &val, ind);
+ 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;
+}
+
+int
+val_eq(struct val a, struct val b, int require_minimal);
+
+#endif /* BTCS_VAL_H */
