diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/ethereum/serpent-go')
80 files changed, 6807 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/.gitignore b/Godeps/_workspace/src/github.com/ethereum/serpent-go/.gitignore new file mode 100644 index 000000000..5d02b54e5 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/.gitignore @@ -0,0 +1,5 @@ +/tmp +*/**/*un~ +*un~ +.DS_Store +*/**/.DS_Store diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/.gitmodules b/Godeps/_workspace/src/github.com/ethereum/serpent-go/.gitmodules new file mode 100644 index 000000000..054c7d628 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/.gitmodules @@ -0,0 +1,3 @@ +[submodule "serp"] + path = serpent + url = https://github.com/ethereum/serpent.git diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/README.md b/Godeps/_workspace/src/github.com/ethereum/serpent-go/README.md new file mode 100644 index 000000000..404f1b380 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/README.md @@ -0,0 +1,12 @@ +[serpent](https://github.com/ethereum/serpent) go bindings. + +## Build instructions + +``` +go get -d github.com/ethereum/serpent-go +cd $GOPATH/src/github.com/ethereum/serpent-go +git submodule init +git submodule update +``` + +You're now ready to go :-) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/all.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/all.cpp new file mode 100644 index 000000000..80032f900 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/all.cpp @@ -0,0 +1,16 @@ +#include "serpent/bignum.cpp" +#include "serpent/util.cpp" +#include "serpent/tokenize.cpp" +#include "serpent/parser.cpp" +#include "serpent/compiler.cpp" +#include "serpent/funcs.cpp" +#include "serpent/lllparser.cpp" +#include "serpent/rewriter.cpp" + +#include "serpent/opcodes.cpp" +#include "serpent/optimize.cpp" +#include "serpent/functions.cpp" +#include "serpent/preprocess.cpp" +#include "serpent/rewriteutils.cpp" + +#include "cpp/api.cpp" diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/cpp/api.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/cpp/api.cpp new file mode 100644 index 000000000..bd2c85c7d --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/cpp/api.cpp @@ -0,0 +1,26 @@ +#include <string> + +#include "serpent/lllparser.h" +#include "serpent/bignum.h" +#include "serpent/util.h" +#include "serpent/tokenize.h" +#include "serpent/parser.h" +#include "serpent/compiler.h" + +#include "cpp/api.h" + +const char *compileGo(char *code, int *err) +{ + try { + std::string c = binToHex(compile(std::string(code))); + + return c.c_str(); + } + catch(std::string &error) { + *err = 1; + return error.c_str(); + } + catch(...) { + return "Unknown error"; + } +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/cpp/api.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/cpp/api.h new file mode 100644 index 000000000..235b5eb4a --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/cpp/api.h @@ -0,0 +1,14 @@ +#ifndef CPP_API_H +#define CPP_API_H + +#ifdef __cplusplus +extern "C" { +#endif + +const char *compileGo(char *code, int *err); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent.go b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent.go new file mode 100644 index 000000000..39b60eed7 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent.go @@ -0,0 +1,27 @@ +package serpent + +// #cgo CXXFLAGS: -I. -Ilangs/ -std=c++0x -Wall -fno-strict-aliasing +// #cgo LDFLAGS: -lstdc++ +// +// #include "cpp/api.h" +// +import "C" + +import ( + "encoding/hex" + "errors" + "unsafe" +) + +func Compile(str string) ([]byte, error) { + var err C.int + out := C.GoString(C.compileGo(C.CString(str), (*C.int)(unsafe.Pointer(&err)))) + + if err == C.int(1) { + return nil, errors.New(out) + } + + bytes, _ := hex.DecodeString(out) + + return bytes, nil +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/.gitignore b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/.gitignore new file mode 100644 index 000000000..72b65e446 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/.gitignore @@ -0,0 +1,12 @@ +[._]*.s[a-w][a-z] +[._]s[a-w][a-z] +*.un~ +Session.vim +.netrwhist +*~ +*.o +serpent +libserpent.a +pyserpent.so +dist +*.egg-info diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/MANIFEST.in b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/MANIFEST.in new file mode 100644 index 000000000..5f5766ced --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/MANIFEST.in @@ -0,0 +1,5 @@ +include *.cpp +include *.h +include *py +include README.md +include Makefile diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/Makefile b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/Makefile new file mode 100644 index 000000000..28c38728e --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/Makefile @@ -0,0 +1,55 @@ +PLATFORM_OPTS = +PYTHON = /usr/include/python2.7 +CXXFLAGS = -fPIC +# -g3 -O0 +BOOST_INC = /usr/include +BOOST_LIB = /usr/lib +TARGET = pyserpent +COMMON_OBJS = bignum.o util.o tokenize.o lllparser.o parser.o opcodes.o optimize.o functions.o rewriteutils.o preprocess.o rewriter.o compiler.o funcs.o +HEADERS = bignum.h util.h tokenize.h lllparser.h parser.h opcodes.h functions.h optimize.h rewriteutils.h preprocess.h rewriter.h compiler.h funcs.h +PYTHON_VERSION = 2.7 + +serpent : serpentc lib + +lib: + ar rvs libserpent.a $(COMMON_OBJS) + g++ $(CXXFLAGS) -shared $(COMMON_OBJS) -o libserpent.so + +serpentc: $(COMMON_OBJS) cmdline.o + rm -rf serpent + g++ -Wall $(COMMON_OBJS) cmdline.o -o serpent + +bignum.o : bignum.cpp bignum.h + +opcodes.o : opcodes.cpp opcodes.h + +util.o : util.cpp util.h bignum.o + +tokenize.o : tokenize.cpp tokenize.h util.o + +lllparser.o : lllparser.cpp lllparser.h tokenize.o util.o + +parser.o : parser.cpp parser.h tokenize.o util.o + +rewriter.o : rewriter.cpp rewriter.h lllparser.o util.o rewriteutils.o preprocess.o opcodes.o functions.o + +preprocessor.o: rewriteutils.o functions.o + +compiler.o : compiler.cpp compiler.h util.o + +funcs.o : funcs.cpp funcs.h + +cmdline.o: cmdline.cpp + +pyext.o: pyext.cpp + +clean: + rm -f serpent *\.o libserpent.a libserpent.so + +install: + cp serpent /usr/local/bin + cp libserpent.a /usr/local/lib + cp libserpent.so /usr/local/lib + rm -rf /usr/local/include/libserpent + mkdir -p /usr/local/include/libserpent + cp $(HEADERS) /usr/local/include/libserpent diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/README.md b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/README.md new file mode 100644 index 000000000..03dfcc15f --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/README.md @@ -0,0 +1,3 @@ +Installation: + +```make && sudo make install``` diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/bignum.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/bignum.cpp new file mode 100644 index 000000000..108b1eb04 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/bignum.cpp @@ -0,0 +1,112 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "bignum.h" + +//Integer to string conversion +std::string unsignedToDecimal(unsigned branch) { + if (branch < 10) return nums.substr(branch, 1); + else return unsignedToDecimal(branch / 10) + nums.substr(branch % 10,1); +} + +//Add two strings representing decimal values +std::string decimalAdd(std::string a, std::string b) { + std::string o = a; + while (b.length() < a.length()) b = "0" + b; + while (o.length() < b.length()) o = "0" + o; + bool carry = false; + for (int i = o.length() - 1; i >= 0; i--) { + o[i] = o[i] + b[i] - '0'; + if (carry) o[i]++; + if (o[i] > '9') { + o[i] -= 10; + carry = true; + } + else carry = false; + } + if (carry) o = "1" + o; + return o; +} + +//Helper function for decimalMul +std::string decimalDigitMul(std::string a, int dig) { + if (dig == 0) return "0"; + else return decimalAdd(a, decimalDigitMul(a, dig - 1)); +} + +//Multiply two strings representing decimal values +std::string decimalMul(std::string a, std::string b) { + std::string o = "0"; + for (unsigned i = 0; i < b.length(); i++) { + std::string n = decimalDigitMul(a, b[i] - '0'); + if (n != "0") { + for (unsigned j = i + 1; j < b.length(); j++) n += "0"; + } + o = decimalAdd(o, n); + } + return o; +} + +//Modexp +std::string decimalModExp(std::string b, std::string e, std::string m) { + if (e == "0") return "1"; + else if (e == "1") return b; + else if (decimalMod(e, "2") == "0") { + std::string o = decimalModExp(b, decimalDiv(e, "2"), m); + return decimalMod(decimalMul(o, o), m); + } + else { + std::string o = decimalModExp(b, decimalDiv(e, "2"), m); + return decimalMod(decimalMul(decimalMul(o, o), b), m); + } +} + +//Is a greater than b? Flag allows equality +bool decimalGt(std::string a, std::string b, bool eqAllowed) { + if (a == b) return eqAllowed; + return (a.length() > b.length()) || (a.length() >= b.length() && a > b); +} + +//Subtract the two strings representing decimal values +std::string decimalSub(std::string a, std::string b) { + if (b == "0") return a; + if (b == a) return "0"; + while (b.length() < a.length()) b = "0" + b; + std::string c = b; + for (unsigned i = 0; i < c.length(); i++) c[i] = '0' + ('9' - c[i]); + std::string o = decimalAdd(decimalAdd(a, c).substr(1), "1"); + while (o.size() > 1 && o[0] == '0') o = o.substr(1); + return o; +} + +//Divide the two strings representing decimal values +std::string decimalDiv(std::string a, std::string b) { + std::string c = b; + if (decimalGt(c, a)) return "0"; + int zeroes = -1; + while (decimalGt(a, c, true)) { + zeroes += 1; + c = c + "0"; + } + c = c.substr(0, c.size() - 1); + std::string quot = "0"; + while (decimalGt(a, c, true)) { + a = decimalSub(a, c); + quot = decimalAdd(quot, "1"); + } + for (int i = 0; i < zeroes; i++) quot += "0"; + return decimalAdd(quot, decimalDiv(a, b)); +} + +//Modulo the two strings representing decimal values +std::string decimalMod(std::string a, std::string b) { + return decimalSub(a, decimalMul(decimalDiv(a, b), b)); +} + +//String to int conversion +unsigned decimalToUnsigned(std::string a) { + if (a.size() == 0) return 0; + else return (a[a.size() - 1] - '0') + + decimalToUnsigned(a.substr(0,a.size()-1)) * 10; +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/bignum.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/bignum.h new file mode 100644 index 000000000..99571acd2 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/bignum.h @@ -0,0 +1,41 @@ +#ifndef ETHSERP_BIGNUM +#define ETHSERP_BIGNUM + +const std::string nums = "0123456789"; + +const std::string tt256 = +"115792089237316195423570985008687907853269984665640564039457584007913129639936" +; + +const std::string tt256m1 = +"115792089237316195423570985008687907853269984665640564039457584007913129639935" +; + +const std::string tt255 = +"57896044618658097711785492504343953926634992332820282019728792003956564819968"; + +const std::string tt176 = +"95780971304118053647396689196894323976171195136475136"; + +std::string unsignedToDecimal(unsigned branch); + +std::string decimalAdd(std::string a, std::string b); + +std::string decimalMul(std::string a, std::string b); + +std::string decimalSub(std::string a, std::string b); + +std::string decimalDiv(std::string a, std::string b); + +std::string decimalMod(std::string a, std::string b); + +std::string decimalModExp(std::string b, std::string e, std::string m); + +bool decimalGt(std::string a, std::string b, bool eqAllowed=false); + +unsigned decimalToUnsigned(std::string a); + +#define utd unsignedToDecimal +#define dtu decimalToUnsigned + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/cmdline.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/cmdline.cpp new file mode 100644 index 000000000..fe2560830 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/cmdline.cpp @@ -0,0 +1,132 @@ +#include <stdio.h> +#include <string> +#include <iostream> +#include <vector> +#include <map> +#include "funcs.h" + +int main(int argv, char** argc) { + if (argv == 1) { + std::cerr << "Must provide a command and arguments! Try parse, rewrite, compile, assemble\n"; + return 0; + } + if (argv == 2 && std::string(argc[1]) == "--help" || std::string(argc[1]) == "-h" ) { + std::cout << argc[1] << "\n"; + + std::cout << "serpent command input\n"; + std::cout << "where input -s for from stdin, a file, or interpreted as serpent code if does not exist as file."; + std::cout << "where command: \n"; + std::cout << " parse: Just parses and returns s-expression code.\n"; + std::cout << " rewrite: Parse, use rewrite rules print s-expressions of result.\n"; + std::cout << " compile: Return resulting compiled EVM code in hex.\n"; + std::cout << " assemble: Return result from step before compilation.\n"; + return 0; + } + + std::string flag = ""; + std::string command = argc[1]; + std::string input; + std::string secondInput; + if (std::string(argc[1]) == "-s") { + flag = command.substr(1); + command = argc[2]; + input = ""; + std::string line; + while (std::getline(std::cin, line)) { + input += line + "\n"; + } + secondInput = argv == 3 ? "" : argc[3]; + } + else { + if (argv == 2) { + std::cerr << "Not enough arguments for serpent cmdline\n"; + throw(0); + } + input = argc[2]; + secondInput = argv == 3 ? "" : argc[3]; + } + bool haveSec = secondInput.length() > 0; + if (command == "parse" || command == "parse_serpent") { + std::cout << printAST(parseSerpent(input), haveSec) << "\n"; + } + else if (command == "rewrite") { + std::cout << printAST(rewrite(parseLLL(input, true)), haveSec) << "\n"; + } + else if (command == "compile_to_lll") { + std::cout << printAST(compileToLLL(input), haveSec) << "\n"; + } + else if (command == "rewrite_chunk") { + std::cout << printAST(rewriteChunk(parseLLL(input, true)), haveSec) << "\n"; + } + else if (command == "compile_chunk_to_lll") { + std::cout << printAST(compileChunkToLLL(input), haveSec) << "\n"; + } + else if (command == "build_fragtree") { + std::cout << printAST(buildFragmentTree(parseLLL(input, true))) << "\n"; + } + else if (command == "compile_lll") { + std::cout << binToHex(compileLLL(parseLLL(input, true))) << "\n"; + } + else if (command == "dereference") { + std::cout << printAST(dereference(parseLLL(input, true)), haveSec) <<"\n"; + } + else if (command == "pretty_assemble") { + std::cout << printTokens(prettyAssemble(parseLLL(input, true))) <<"\n"; + } + else if (command == "pretty_compile_lll") { + std::cout << printTokens(prettyCompileLLL(parseLLL(input, true))) << "\n"; + } + else if (command == "pretty_compile") { + std::cout << printTokens(prettyCompile(input)) << "\n"; + } + else if (command == "pretty_compile_chunk") { + std::cout << printTokens(prettyCompileChunk(input)) << "\n"; + } + else if (command == "assemble") { + std::cout << assemble(parseLLL(input, true)) << "\n"; + } + else if (command == "serialize") { + std::cout << binToHex(serialize(tokenize(input, Metadata(), false))) << "\n"; + } + else if (command == "flatten") { + std::cout << printTokens(flatten(parseLLL(input, true))) << "\n"; + } + else if (command == "deserialize") { + std::cout << printTokens(deserialize(hexToBin(input))) << "\n"; + } + else if (command == "compile") { + std::cout << binToHex(compile(input)) << "\n"; + } + else if (command == "compile_chunk") { + std::cout << binToHex(compileChunk(input)) << "\n"; + } + else if (command == "encode_datalist") { + std::vector<Node> tokens = tokenize(input); + std::vector<std::string> o; + for (int i = 0; i < (int)tokens.size(); i++) { + o.push_back(tokens[i].val); + } + std::cout << binToHex(encodeDatalist(o)) << "\n"; + } + else if (command == "decode_datalist") { + std::vector<std::string> o = decodeDatalist(hexToBin(input)); + std::vector<Node> tokens; + for (int i = 0; i < (int)o.size(); i++) + tokens.push_back(token(o[i])); + std::cout << printTokens(tokens) << "\n"; + } + else if (command == "tokenize") { + std::cout << printTokens(tokenize(input)); + } + else if (command == "biject") { + if (argv == 3) + std::cerr << "Not enough arguments for biject\n"; + int pos = decimalToUnsigned(secondInput); + std::vector<Node> n = prettyCompile(input); + if (pos >= (int)n.size()) + std::cerr << "Code position too high\n"; + Metadata m = n[pos].metadata; + std::cout << "Opcode: " << n[pos].val << ", file: " << m.file << + ", line: " << m.ln << ", char: " << m.ch << "\n"; + } +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/compiler.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/compiler.cpp new file mode 100644 index 000000000..b9281dcbc --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/compiler.cpp @@ -0,0 +1,554 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "bignum.h" +#include "opcodes.h" + +struct programAux { + std::map<std::string, std::string> vars; + int nextVarMem; + bool allocUsed; + bool calldataUsed; + int step; + int labelLength; +}; + +struct programVerticalAux { + int height; + std::string innerScopeName; + std::map<std::string, int> dupvars; + std::map<std::string, int> funvars; + std::vector<mss> scopes; +}; + +struct programData { + programAux aux; + Node code; + int outs; +}; + +programAux Aux() { + programAux o; + o.allocUsed = false; + o.calldataUsed = false; + o.step = 0; + o.nextVarMem = 32; + return o; +} + +programVerticalAux verticalAux() { + programVerticalAux o; + o.height = 0; + o.dupvars = std::map<std::string, int>(); + o.funvars = std::map<std::string, int>(); + o.scopes = std::vector<mss>(); + return o; +} + +programData pd(programAux aux = Aux(), Node code=token("_"), int outs=0) { + programData o; + o.aux = aux; + o.code = code; + o.outs = outs; + return o; +} + +Node multiToken(Node nodes[], int len, Metadata met) { + std::vector<Node> out; + for (int i = 0; i < len; i++) { + out.push_back(nodes[i]); + } + return astnode("_", out, met); +} + +Node finalize(programData c); + +Node popwrap(Node node) { + Node nodelist[] = { + node, + token("POP", node.metadata) + }; + return multiToken(nodelist, 2, node.metadata); +} + +// Grabs variables +mss getVariables(Node node, mss cur=mss()) { + Metadata m = node.metadata; + // Tokens don't contain any variables + if (node.type == TOKEN) + return cur; + // Don't descend into call fragments + else if (node.val == "lll") + return getVariables(node.args[1], cur); + // At global scope get/set/ref also declare + else if (node.val == "get" || node.val == "set" || node.val == "ref") { + if (node.args[0].type != TOKEN) + err("Variable name must be simple token," + " not complex expression!", m); + if (!cur.count(node.args[0].val)) { + cur[node.args[0].val] = utd(cur.size() * 32 + 32); + //std::cerr << node.args[0].val << " " << cur[node.args[0].val] << "\n"; + } + } + // Recursively process children + for (unsigned i = 0; i < node.args.size(); i++) { + cur = getVariables(node.args[i], cur); + } + return cur; +} + +// Turns LLL tree into tree of code fragments +programData opcodeify(Node node, + programAux aux=Aux(), + programVerticalAux vaux=verticalAux()) { + std::string symb = "_"+mkUniqueToken(); + Metadata m = node.metadata; + // Get variables + if (!aux.vars.size()) { + aux.vars = getVariables(node); + aux.nextVarMem = aux.vars.size() * 32 + 32; + } + // Numbers + if (node.type == TOKEN) { + return pd(aux, nodeToNumeric(node), 1); + } + else if (node.val == "ref" || node.val == "get" || node.val == "set") { + std::string varname = node.args[0].val; + // Determine reference to variable + Node varNode = tkn(aux.vars[varname], m); + //std::cerr << varname << " " << printSimple(varNode) << "\n"; + // Set variable + if (node.val == "set") { + programData sub = opcodeify(node.args[1], aux, vaux); + if (!sub.outs) + err("Value to set variable must have nonzero arity!", m); + // What if we are setting a stack variable? + if (vaux.dupvars.count(node.args[0].val)) { + int h = vaux.height - vaux.dupvars[node.args[0].val]; + if (h > 16) err("Too deep for stack variable (max 16)", m); + Node nodelist[] = { + sub.code, + token("SWAP"+unsignedToDecimal(h), m), + token("POP", m) + }; + return pd(sub.aux, multiToken(nodelist, 3, m), 0); + } + // Setting a memory variable + else { + Node nodelist[] = { + sub.code, + varNode, + token("MSTORE", m), + }; + return pd(sub.aux, multiToken(nodelist, 3, m), 0); + } + } + // Get variable + else if (node.val == "get") { + // Getting a stack variable + if (vaux.dupvars.count(node.args[0].val)) { + int h = vaux.height - vaux.dupvars[node.args[0].val]; + if (h > 16) err("Too deep for stack variable (max 16)", m); + return pd(aux, token("DUP"+unsignedToDecimal(h)), 1); + } + // Getting a memory variable + else { + Node nodelist[] = + { varNode, token("MLOAD", m) }; + return pd(aux, multiToken(nodelist, 2, m), 1); + } + } + // Refer variable + else if (node.val == "ref") { + if (vaux.dupvars.count(node.args[0].val)) + err("Cannot ref stack variable!", m); + return pd(aux, varNode, 1); + } + } + // Comments do nothing + else if (node.val == "comment") { + Node nodelist[] = { }; + return pd(aux, multiToken(nodelist, 0, m), 0); + } + // Custom operation sequence + // eg. (ops bytez id msize swap1 msize add 0 swap1 mstore) == alloc + if (node.val == "ops") { + std::vector<Node> subs2; + int depth = 0; + for (unsigned i = 0; i < node.args.size(); i++) { + std::string op = upperCase(node.args[i].val); + if (node.args[i].type == ASTNODE || opinputs(op) == -1) { + programVerticalAux vaux2 = vaux; + vaux2.height = vaux.height - i - 1 + node.args.size(); + programData sub = opcodeify(node.args[i], aux, vaux2); + aux = sub.aux; + depth += sub.outs; + subs2.push_back(sub.code); + } + else { + subs2.push_back(token(op, m)); + depth += opoutputs(op) - opinputs(op); + } + } + if (depth < 0 || depth > 1) err("Stack depth mismatch", m); + return pd(aux, astnode("_", subs2, m), 0); + } + // Code blocks + if (node.val == "lll" && node.args.size() == 2) { + if (node.args[1].val != "0") aux.allocUsed = true; + std::vector<Node> o; + o.push_back(finalize(opcodeify(node.args[0]))); + programData sub = opcodeify(node.args[1], aux, vaux); + Node code = astnode("____CODE", o, m); + Node nodelist[] = { + token("$begincode"+symb+".endcode"+symb, m), token("DUP1", m), + token("$begincode"+symb, m), sub.code, token("CODECOPY", m), + token("$endcode"+symb, m), token("JUMP", m), + token("~begincode"+symb, m), code, + token("~endcode"+symb, m), token("JUMPDEST", m) + }; + return pd(sub.aux, multiToken(nodelist, 11, m), 1); + } + // Stack variables + if (node.val == "with") { + programData initial = opcodeify(node.args[1], aux, vaux); + programVerticalAux vaux2 = vaux; + vaux2.dupvars[node.args[0].val] = vaux.height; + vaux2.height += 1; + if (!initial.outs) + err("Initial variable value must have nonzero arity!", m); + programData sub = opcodeify(node.args[2], initial.aux, vaux2); + Node nodelist[] = { + initial.code, + sub.code + }; + programData o = pd(sub.aux, multiToken(nodelist, 2, m), sub.outs); + if (sub.outs) + o.code.args.push_back(token("SWAP1", m)); + o.code.args.push_back(token("POP", m)); + return o; + } + // Seq of multiple statements + if (node.val == "seq") { + std::vector<Node> children; + int lastOut = 0; + for (unsigned i = 0; i < node.args.size(); i++) { + programData sub = opcodeify(node.args[i], aux, vaux); + aux = sub.aux; + if (sub.outs == 1) { + if (i < node.args.size() - 1) sub.code = popwrap(sub.code); + else lastOut = 1; + } + children.push_back(sub.code); + } + return pd(aux, astnode("_", children, m), lastOut); + } + // 2-part conditional (if gets rewritten to unless in rewrites) + else if (node.val == "unless" && node.args.size() == 2) { + programData cond = opcodeify(node.args[0], aux, vaux); + programData action = opcodeify(node.args[1], cond.aux, vaux); + aux = action.aux; + if (!cond.outs) err("Condition of if/unless statement has arity 0", m); + if (action.outs) action.code = popwrap(action.code); + Node nodelist[] = { + cond.code, + token("$endif"+symb, m), token("JUMPI", m), + action.code, + token("~endif"+symb, m), token("JUMPDEST", m) + }; + return pd(aux, multiToken(nodelist, 6, m), 0); + } + // 3-part conditional + else if (node.val == "if" && node.args.size() == 3) { + programData ifd = opcodeify(node.args[0], aux, vaux); + programData thend = opcodeify(node.args[1], ifd.aux, vaux); + programData elsed = opcodeify(node.args[2], thend.aux, vaux); + aux = elsed.aux; + if (!ifd.outs) + err("Condition of if/unless statement has arity 0", m); + // Handle cases where one conditional outputs something + // and the other does not + int outs = (thend.outs && elsed.outs) ? 1 : 0; + if (thend.outs > outs) thend.code = popwrap(thend.code); + if (elsed.outs > outs) elsed.code = popwrap(elsed.code); + Node nodelist[] = { + ifd.code, + token("ISZERO", m), + token("$else"+symb, m), token("JUMPI", m), + thend.code, + token("$endif"+symb, m), token("JUMP", m), + token("~else"+symb, m), token("JUMPDEST", m), + elsed.code, + token("~endif"+symb, m), token("JUMPDEST", m) + }; + return pd(aux, multiToken(nodelist, 12, m), outs); + } + // While (rewritten to this in rewrites) + else if (node.val == "until") { + programData cond = opcodeify(node.args[0], aux, vaux); + programData action = opcodeify(node.args[1], cond.aux, vaux); + aux = action.aux; + if (!cond.outs) + err("Condition of while/until loop has arity 0", m); + if (action.outs) action.code = popwrap(action.code); + Node nodelist[] = { + token("~beg"+symb, m), token("JUMPDEST", m), + cond.code, + token("$end"+symb, m), token("JUMPI", m), + action.code, + token("$beg"+symb, m), token("JUMP", m), + token("~end"+symb, m), token("JUMPDEST", m), + }; + return pd(aux, multiToken(nodelist, 10, m)); + } + // Memory allocations + else if (node.val == "alloc") { + programData bytez = opcodeify(node.args[0], aux, vaux); + aux = bytez.aux; + if (!bytez.outs) + err("Alloc input has arity 0", m); + aux.allocUsed = true; + Node nodelist[] = { + bytez.code, + token("MSIZE", m), token("SWAP1", m), token("MSIZE", m), + token("ADD", m), + token("0", m), token("SWAP1", m), token("MSTORE", m) + }; + return pd(aux, multiToken(nodelist, 8, m), 1); + } + // All other functions/operators + else { + std::vector<Node> subs2; + int depth = opinputs(upperCase(node.val)); + if (depth == -1) + err("Not a function or opcode: "+node.val, m); + if ((int)node.args.size() != depth) + err("Invalid arity for "+node.val, m); + for (int i = node.args.size() - 1; i >= 0; i--) { + programVerticalAux vaux2 = vaux; + vaux2.height = vaux.height - i - 1 + node.args.size(); + programData sub = opcodeify(node.args[i], aux, vaux2); + aux = sub.aux; + if (!sub.outs) + err("Input "+unsignedToDecimal(i)+" has arity 0", sub.code.metadata); + subs2.push_back(sub.code); + } + subs2.push_back(token(upperCase(node.val), m)); + int outdepth = opoutputs(upperCase(node.val)); + return pd(aux, astnode("_", subs2, m), outdepth); + } +} + +// Adds necessary wrappers to a program +Node finalize(programData c) { + std::vector<Node> bottom; + Metadata m = c.code.metadata; + // If we are using both alloc and variables, we need to pre-zfill + // some memory + if ((c.aux.allocUsed || c.aux.calldataUsed) && c.aux.vars.size() > 0) { + Node nodelist[] = { + token("0", m), + token(unsignedToDecimal(c.aux.nextVarMem - 1)), + token("MSTORE8", m) + }; + bottom.push_back(multiToken(nodelist, 3, m)); + } + // The actual code + bottom.push_back(c.code); + return astnode("_", bottom, m); +} + +//LLL -> code fragment tree +Node buildFragmentTree(Node node) { + return finalize(opcodeify(node)); +} + + +// Builds a dictionary mapping labels to variable names +programAux buildDict(Node program, programAux aux, int labelLength) { + Metadata m = program.metadata; + // Token + if (program.type == TOKEN) { + if (isNumberLike(program)) { + aux.step += 1 + toByteArr(program.val, m).size(); + } + else if (program.val[0] == '~') { + aux.vars[program.val.substr(1)] = unsignedToDecimal(aux.step); + } + else if (program.val[0] == '$') { + aux.step += labelLength + 1; + } + else aux.step += 1; + } + // A sub-program (ie. LLL) + else if (program.val == "____CODE") { + programAux auks = Aux(); + for (unsigned i = 0; i < program.args.size(); i++) { + auks = buildDict(program.args[i], auks, labelLength); + } + for (std::map<std::string,std::string>::iterator it=auks.vars.begin(); + it != auks.vars.end(); + it++) { + aux.vars[(*it).first] = (*it).second; + } + aux.step += auks.step; + } + // Normal sub-block + else { + for (unsigned i = 0; i < program.args.size(); i++) { + aux = buildDict(program.args[i], aux, labelLength); + } + } + return aux; +} + +// Applies that dictionary +Node substDict(Node program, programAux aux, int labelLength) { + Metadata m = program.metadata; + std::vector<Node> out; + std::vector<Node> inner; + if (program.type == TOKEN) { + if (program.val[0] == '$') { + std::string tokStr = "PUSH"+unsignedToDecimal(labelLength); + out.push_back(token(tokStr, m)); + int dotLoc = program.val.find('.'); + if (dotLoc == -1) { + std::string val = aux.vars[program.val.substr(1)]; + inner = toByteArr(val, m, labelLength); + } + else { + std::string start = aux.vars[program.val.substr(1, dotLoc-1)], + end = aux.vars[program.val.substr(dotLoc + 1)], + dist = decimalSub(end, start); + inner = toByteArr(dist, m, labelLength); + } + out.push_back(astnode("_", inner, m)); + } + else if (program.val[0] == '~') { } + else if (isNumberLike(program)) { + inner = toByteArr(program.val, m); + out.push_back(token("PUSH"+unsignedToDecimal(inner.size()))); + out.push_back(astnode("_", inner, m)); + } + else return program; + } + else { + for (unsigned i = 0; i < program.args.size(); i++) { + Node n = substDict(program.args[i], aux, labelLength); + if (n.type == TOKEN || n.args.size()) out.push_back(n); + } + } + return astnode("_", out, m); +} + +// Compiled fragtree -> compiled fragtree without labels +Node dereference(Node program) { + int sz = treeSize(program) * 4; + int labelLength = 1; + while (sz >= 256) { labelLength += 1; sz /= 256; } + programAux aux = buildDict(program, Aux(), labelLength); + return substDict(program, aux, labelLength); +} + +// Dereferenced fragtree -> opcodes +std::vector<Node> flatten(Node derefed) { + std::vector<Node> o; + if (derefed.type == TOKEN) { + o.push_back(derefed); + } + else { + for (unsigned i = 0; i < derefed.args.size(); i++) { + std::vector<Node> oprime = flatten(derefed.args[i]); + for (unsigned j = 0; j < oprime.size(); j++) o.push_back(oprime[j]); + } + } + return o; +} + +// Opcodes -> bin +std::string serialize(std::vector<Node> codons) { + std::string o; + for (unsigned i = 0; i < codons.size(); i++) { + int v; + if (isNumberLike(codons[i])) { + v = decimalToUnsigned(codons[i].val); + } + else if (codons[i].val.substr(0,4) == "PUSH") { + v = 95 + decimalToUnsigned(codons[i].val.substr(4)); + } + else { + v = opcode(codons[i].val); + } + o += (char)v; + } + return o; +} + +// Bin -> opcodes +std::vector<Node> deserialize(std::string ser) { + std::vector<Node> o; + int backCount = 0; + for (unsigned i = 0; i < ser.length(); i++) { + unsigned char v = (unsigned char)ser[i]; + std::string oper = op((int)v); + if (oper != "" && backCount <= 0) o.push_back(token(oper)); + else if (v >= 96 && v < 128 && backCount <= 0) { + o.push_back(token("PUSH"+unsignedToDecimal(v - 95))); + } + else o.push_back(token(unsignedToDecimal(v))); + if (v >= 96 && v < 128 && backCount <= 0) { + backCount = v - 95; + } + else backCount--; + } + return o; +} + +// Fragtree -> bin +std::string assemble(Node fragTree) { + return serialize(flatten(dereference(fragTree))); +} + +// Fragtree -> tokens +std::vector<Node> prettyAssemble(Node fragTree) { + return flatten(dereference(fragTree)); +} + +// LLL -> bin +std::string compileLLL(Node program) { + return assemble(buildFragmentTree(program)); +} + +// LLL -> tokens +std::vector<Node> prettyCompileLLL(Node program) { + return prettyAssemble(buildFragmentTree(program)); +} + +// Converts a list of integer values to binary transaction data +std::string encodeDatalist(std::vector<std::string> vals) { + std::string o; + for (unsigned i = 0; i < vals.size(); i++) { + std::vector<Node> n = toByteArr(strToNumeric(vals[i]), Metadata(), 32); + for (unsigned j = 0; j < n.size(); j++) { + int v = decimalToUnsigned(n[j].val); + o += (char)v; + } + } + return o; +} + +// Converts binary transaction data into a list of integer values +std::vector<std::string> decodeDatalist(std::string ser) { + std::vector<std::string> out; + for (unsigned i = 0; i < ser.length(); i+= 32) { + std::string o = "0"; + for (unsigned j = i; j < i + 32; j++) { + int vj = (int)(unsigned char)ser[j]; + o = decimalAdd(decimalMul(o, "256"), unsignedToDecimal(vj)); + } + out.push_back(o); + } + return out; +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/compiler.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/compiler.h new file mode 100644 index 000000000..aecaa3718 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/compiler.h @@ -0,0 +1,43 @@ +#ifndef ETHSERP_COMPILER +#define ETHSERP_COMPILER + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// Compiled fragtree -> compiled fragtree without labels +Node dereference(Node program); + +// LLL -> fragtree +Node buildFragmentTree(Node program); + +// Dereferenced fragtree -> opcodes +std::vector<Node> flatten(Node derefed); + +// opcodes -> bin +std::string serialize(std::vector<Node> codons); + +// Fragtree -> bin +std::string assemble(Node fragTree); + +// Fragtree -> opcodes +std::vector<Node> prettyAssemble(Node fragTree); + +// LLL -> bin +std::string compileLLL(Node program); + +// LLL -> opcodes +std::vector<Node> prettyCompileLLL(Node program); + +// bin -> opcodes +std::vector<Node> deserialize(std::string ser); + +// Converts a list of integer values to binary transaction data +std::string encodeDatalist(std::vector<std::string> vals); + +// Converts binary transaction data into a list of integer values +std::vector<std::string> decodeDatalist(std::string ser); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/example.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/example.cpp new file mode 100644 index 000000000..1ce2590d0 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/example.cpp @@ -0,0 +1,11 @@ +#include <libserpent/funcs.h> +#include <libserpent/bignum.h> +#include <iostream> + +using namespace std; + +int main() { + cout << printAST(compileToLLL(get_file_contents("examples/namecoin.se"))) << "\n"; + cout << decimalSub("10234", "10234") << "\n"; + cout << decimalSub("10234", "10233") << "\n"; +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/collatz.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/collatz.se new file mode 100644 index 000000000..148b47b59 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/collatz.se @@ -0,0 +1,11 @@ +x = msg.data[0] +steps = 0 + +while x > 1: + steps += 1 + if (x % 2) == 0: + x /= 2 + else: + x = 3 * x + 1 + +return(steps) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/counterparty/counterparty.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/counterparty/counterparty.se new file mode 100644 index 000000000..abec0d102 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/counterparty/counterparty.se @@ -0,0 +1,274 @@ +# Ethereum forks Counterparty in 340 lines of serpent +# Not yet tested + +# assets[i] = a registered asset, assets[i].holders[j] = former or current i-holder +data assets[2^50](creator, name, calldate, callprice, dividend_paid, holders[2^50], holdersCount) +data nextAssetId + +# holdersMap: holdersMap[addr][asset] = 1 if addr holds asset +data holdersMap[2^160][2^50] + +# balances[x][y] = how much of y x holds +data balances[2^160][2^50] + +# orders[a][b] = heap of indices to (c, d, e) +# = c offers to sell d units of a at a price of e units of b per 10^18 units +# of a +data orderbooks[2^50][2^50] + +# store of general order data +data orders[2^50](seller, asset_sold, quantity, price) +data ordersCount + +# data feeds +data feeds[2^50](owner, value) +data feedCount + +# heap +data heap +extern heap: [register, push, pop, top, size] + +data cfds[2^50](maker, acceptor, feed, asset, strike, leverage, min, max, maturity) +data cfdCount + +data bets[2^50](maker, acceptor, feed, asset, makerstake, acceptorstake, eqtest, maturity) +data betCount + +def init(): + heap = create('heap.se') + +# Add units (internal method) +def add(to, asset, value): + assert msg.sender == self + self.balances[to][asset] += value + # Add the holder to the holders list + if not self.holdersMap[to][asset]: + self.holdersMap[to][asset] = 1 + c = self.assets[asset].holdersCount + self.assets[asset].holders[c] = to + self.assets[asset].holdersCount = c + 1 + +# Register a new asset +def register_asset(q, name, calldate, callprice): + newid = self.nextAssetId + self.assets[newid].creator = msg.sender + self.assets[newid].name = name + self.assets[newid].calldate = calldate + self.assets[newid].callprice = callprice + self.assets[newid].holders[0] = msg.sender + self.assets[newid].holdersCount = 1 + self.balances[msg.sender][newid] = q + self.holdersMap[msg.sender][newid] = 1 + +# Send +def send(to, asset, value): + fromval = self.balances[msg.sender][asset] + if fromval >= value: + self.balances[msg.sender][asset] -= value + self.add(to, asset, value) + +# Order +def mkorder(selling, buying, quantity, price): + # Make sure you have enough to pay for the order + assert self.balances[msg.sender][selling] >= quantity: + # Try to match existing orders + o = orderbooks[buying][selling] + if not o: + o = self.heap.register() + orderbooks[selling][buying] = o + sz = self.heap.size(o) + invprice = 10^36 / price + while quantity > 0 and sz > 0: + orderid = self.heap.pop() + p = self.orders[orderid].price + if p > invprice: + sz = 0 + else: + q = self.orders[orderid].quantity + oq = min(q, quantity) + b = self.orders[orderid].seller + self.balances[msg.sender][selling] -= oq * p / 10^18 + self.add(msg.sender, buying, oq) + self.add(b, selling, oq * p / 10^18) + self.orders[orderid].quantity = q - oq + if oq == q: + self.orders[orderid].seller = 0 + self.orders[orderid].price = 0 + self.orders[orderid].asset_sold = 0 + quantity -= oq + sz -= 1 + assert quantity > 0 + # Make the order + c = self.ordersCount + self.orders[c].seller = msg.sender + self.orders[c].asset_sold = selling + self.orders[c].quantity = quantity + self.orders[c].price = price + self.ordersCount += 1 + # Add it to the heap + o = orderbooks[selling][buying] + if not o: + o = self.heap.register() + orderbooks[selling][buying] = o + self.balances[msg.sender][selling] -= quantity + self.heap.push(o, price, c) + return(c) + +def cancel_order(id): + if self.orders[id].seller == msg.sender: + self.orders[id].seller = 0 + self.orders[id].price = 0 + self.balances[msg.sender][self.orders[id].asset_sold] += self.orders[id].quantity + self.orders[id].quantity = 0 + self.orders[id].asset_sold = 0 + +def register_feed(): + c = self.feedCount + self.feeds[c].owner = msg.sender + self.feedCount = c + 1 + return(c) + +def set_feed(id, v): + if self.feeds[id].owner == msg.sender: + self.feeds[id].value = v + +def mk_cfd_offer(feed, asset, strike, leverage, min, max, maturity): + b = self.balances[msg.sender][asset] + req = max((strike - min) * leverage, (strike - max) * leverage) + assert b >= req + self.balances[msg.sender][asset] = b - req + c = self.cfdCount + self.cfds[c].maker = msg.sender + self.cfds[c].feed = feed + self.cfds[c].asset = asset + self.cfds[c].strike = strike + self.cfds[c].leverage = leverage + self.cfds[c].min = min + self.cfds[c].max = max + self.cfds[c].maturity = maturity + self.cfdCount = c + 1 + return(c) + +def accept_cfd_offer(c): + assert not self.cfds[c].acceptor and self.cfds[c].maker + asset = self.cfds[c].asset + strike = self.cfds[c].strike + min = self.cfds[c].min + max = self.cfds[c].max + leverage = self.cfds[c].leverage + b = self.balances[msg.sender][asset] + req = max((min - strike) * leverage, (max - strike) * leverage) + assert b >= req + self.balances[msg.sender][asset] = b - req + self.cfds[c].acceptor = msg.sender + self.cfds[c].maturity += block.timestamp + +def claim_cfd_offer(c): + asset = self.cfds[c].asset + strike = self.cfds[c].strike + min = self.cfds[c].min + max = self.cfds[c].max + leverage = self.cfds[c].leverage + v = self.feeds[self.cfds[c].feed].value + assert v <= min or v >= max or block.timestamp >= self.cfds[c].maturity + maker_req = max((strike - min) * leverage, (strike - max) * leverage) + acceptor_req = max((min - strike) * leverage, (max - strike) * leverage) + paydelta = (strike - v) * leverage + self.add(self.cfds[c].maker, asset, maker_req + paydelta) + self.add(self.cfds[c].acceptor, asset, acceptor_req - paydelta) + self.cfds[c].maker = 0 + self.cfds[c].acceptor = 0 + self.cfds[c].feed = 0 + self.cfds[c].asset = 0 + self.cfds[c].strike = 0 + self.cfds[c].leverage = 0 + self.cfds[c].min = 0 + self.cfds[c].max = 0 + self.cfds[c].maturity = 0 + +def withdraw_cfd_offer(c): + if self.cfds[c].maker == msg.sender and not self.cfds[c].acceptor: + asset = self.cfds[c].asset + strike = self.cfds[c].strike + min = self.cfds[c].min + max = self.cfds[c].max + leverage = self.cfds[c].leverage + maker_req = max((strike - min) * leverage, (strike - max) * leverage) + self.balances[self.cfds[c].maker][asset] += maker_req + self.cfds[c].maker = 0 + self.cfds[c].acceptor = 0 + self.cfds[c].feed = 0 + self.cfds[c].asset = 0 + self.cfds[c].strike = 0 + self.cfds[c].leverage = 0 + self.cfds[c].min = 0 + self.cfds[c].max = 0 + self.cfds[c].maturity = 0 + + +def mk_bet_offer(feed, asset, makerstake, acceptorstake, eqtest, maturity): + assert self.balances[msg.sender][asset] >= makerstake + c = self.betCount + self.bets[c].maker = msg.sender + self.bets[c].feed = feed + self.bets[c].asset = asset + self.bets[c].makerstake = makerstake + self.bets[c].acceptorstake = acceptorstake + self.bets[c].eqtest = eqtest + self.bets[c].maturity = maturity + self.balances[msg.sender][asset] -= makerstake + self.betCount = c + 1 + return(c) + +def accept_bet_offer(c): + assert self.bets[c].maker and not self.bets[c].acceptor + asset = self.bets[c].asset + acceptorstake = self.bets[c].acceptorstake + assert self.balances[msg.sender][asset] >= acceptorstake + self.balances[msg.sender][asset] -= acceptorstake + self.bets[c].acceptor = msg.sender + +def claim_bet_offer(c): + assert block.timestamp >= self.bets[c].maturity + v = self.feeds[self.bets[c].feed].value + totalstake = self.bets[c].makerstake + self.bets[c].acceptorstake + if v == self.bets[c].eqtest: + self.add(self.bets[c].maker, self.bets[c].asset, totalstake) + else: + self.add(self.bets[c].acceptor, self.bets[c].asset, totalstake) + self.bets[c].maker = 0 + self.bets[c].feed = 0 + self.bets[c].asset = 0 + self.bets[c].makerstake = 0 + self.bets[c].acceptorstake = 0 + self.bets[c].eqtest = 0 + self.bets[c].maturity = 0 + +def cancel_bet(c): + assert not self.bets[c].acceptor and msg.sender == self.bets[c].maker + self.balances[msg.sender][self.bets[c].asset] += self.bets[c].makerstake + self.bets[c].maker = 0 + self.bets[c].feed = 0 + self.bets[c].asset = 0 + self.bets[c].makerstake = 0 + self.bets[c].acceptorstake = 0 + self.bets[c].eqtest = 0 + self.bets[c].maturity = 0 + +def dividend(holder_asset, divvying_asset, ratio): + i = 0 + sz = self.assets[holder_asset].holdersCount + t = 0 + holders = array(sz) + payments = array(sz) + while i < sz: + holders[i] = self.assets[holder_asset].holders[i] + payments[i] = self.balances[holders[i]][holder_asset] * ratio / 10^18 + t += payments[i] + i += 1 + if self.balances[msg.sender][divvying_asset] >= t: + i = 0 + while i < sz: + self.add(holders[i], divvying_asset, payments[i]) + i += 1 + self.balances[msg.sender][divvying_asset] -= t diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/counterparty/heap.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/counterparty/heap.se new file mode 100644 index 000000000..4a43a3974 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/counterparty/heap.se @@ -0,0 +1,69 @@ +data heaps[2^50](owner, size, nodes[2^50](key, value)) +data heapIndex + +def register(): + i = self.heapIndex + self.heaps[i].owner = msg.sender + self.heapIndex = i + 1 + return(i) + +def push(heap, key, value): + assert msg.sender == self.heaps[heap].owner + sz = self.heaps[heap].size + self.heaps[heap].nodes[sz].key = key + self.heaps[heap].nodes[sz].value = value + k = sz + 1 + while k > 1: + bottom = self.heaps[heap].nodes[k].key + top = self.heaps[heap].nodes[k/2].key + if bottom < top: + tvalue = self.heaps[heap].nodes[k/2].value + bvalue = self.heaps[heap].nodes[k].value + self.heaps[heap].nodes[k].key = top + self.heaps[heap].nodes[k].value = tvalue + self.heaps[heap].nodes[k/2].key = bottom + self.heaps[heap].nodes[k/2].value = bvalue + k /= 2 + else: + k = 0 + self.heaps[heap].size = sz + 1 + +def pop(heap): + sz = self.heaps[heap].size + assert sz + prevtop = self.heaps[heap].nodes[1].value + self.heaps[heap].nodes[1].key = self.heaps[heap].nodes[sz].key + self.heaps[heap].nodes[1].value = self.heaps[heap].nodes[sz].value + self.heaps[heap].nodes[sz].key = 0 + self.heaps[heap].nodes[sz].value = 0 + top = self.heaps[heap].nodes[1].key + k = 1 + while k * 2 < sz: + bottom1 = self.heaps[heap].nodes[k * 2].key + bottom2 = self.heaps[heap].nodes[k * 2 + 1].key + if bottom1 < top and (bottom1 < bottom2 or k * 2 + 1 >= sz): + tvalue = self.heaps[heap].nodes[1].value + bvalue = self.heaps[heap].nodes[k * 2].value + self.heaps[heap].nodes[k].key = bottom1 + self.heaps[heap].nodes[k].value = bvalue + self.heaps[heap].nodes[k * 2].key = top + self.heaps[heap].nodes[k * 2].value = tvalue + k = k * 2 + elif bottom2 < top and bottom2 < bottom1 and k * 2 + 1 < sz: + tvalue = self.heaps[heap].nodes[1].value + bvalue = self.heaps[heap].nodes[k * 2 + 1].value + self.heaps[heap].nodes[k].key = bottom2 + self.heaps[heap].nodes[k].value = bvalue + self.heaps[heap].nodes[k * 2 + 1].key = top + self.heaps[heap].nodes[k * 2 + 1].value = tvalue + k = k * 2 + 1 + else: + k = sz + self.heaps[heap].size = sz - 1 + return(prevtop) + +def top(heap): + return(self.heaps[heap].nodes[1].value) + +def size(heap): + return(self.heaps[heap].size) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/crowdfund.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/crowdfund.se new file mode 100644 index 000000000..9fd1e0643 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/crowdfund.se @@ -0,0 +1,53 @@ +data campaigns[2^80](recipient, goal, deadline, contrib_total, contrib_count, contribs[2^50](sender, value)) + +def create_campaign(id, recipient, goal, timelimit): + if self.campaigns[id].recipient: + return(0) + self.campaigns[id].recipient = recipient + self.campaigns[id].goal = goal + self.campaigns[id].deadline = block.timestamp + timelimit + +def contribute(id): + # Update contribution total + total_contributed = self.campaigns[id].contrib_total + msg.value + self.campaigns[id].contrib_total = total_contributed + + # Record new contribution + sub_index = self.campaigns[id].contrib_count + self.campaigns[id].contribs[sub_index].sender = msg.sender + self.campaigns[id].contribs[sub_index].value = msg.value + self.campaigns[id].contrib_count = sub_index + 1 + + # Enough funding? + if total_contributed >= self.campaigns[id].goal: + send(self.campaigns[id].recipient, total_contributed) + self.clear(id) + return(1) + + # Expired? + if block.timestamp > self.campaigns[id].deadline: + i = 0 + c = self.campaigns[id].contrib_count + while i < c: + send(self.campaigns[id].contribs[i].sender, self.campaigns[id].contribs[i].value) + i += 1 + self.clear(id) + return(2) + +def progress_report(id): + return(self.campaigns[id].contrib_total) + +# Clearing function for internal use +def clear(id): + if self == msg.sender: + self.campaigns[id].recipient = 0 + self.campaigns[id].goal = 0 + self.campaigns[id].deadline = 0 + c = self.campaigns[id].contrib_count + self.campaigns[id].contrib_count = 0 + self.campaigns[id].contrib_total = 0 + i = 0 + while i < c: + self.campaigns[id].contribs[i].sender = 0 + self.campaigns[id].contribs[i].value = 0 + i += 1 diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/futarchy.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/futarchy.se new file mode 100644 index 000000000..0d68622ac --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/futarchy.se @@ -0,0 +1,136 @@ +# 0: current epoch +# 1: number of proposals +# 2: master currency +# 3: last winning market +# 4: last txid +# 5: long-term ema currency units purchased +# 6: last block when currency units purchased +# 7: ether allocated to last round +# 8: last block when currency units claimed +# 9: ether allocated to current round +# 1000+: [proposal address, market ID, totprice, totvolume] + +init: + # We technically have two levels of epoch here. We have + # one epoch of 1000, to synchronize with the 1000 epoch + # of the market, and then 100 of those epochs make a + # meta-epoch (I'll nominate the term "seculum") over + # which the futarchy protocol will take place + contract.storage[0] = block.number / 1000 + # The master currency of the futarchy. The futarchy will + # assign currency units to whoever the prediction market + # thinks will best increase the currency's value + master_currency = create('subcurrency.se') + contract.storage[2] = master_currency +code: + curepoch = block.number / 1000 + prevepoch = contract.storage[0] + if curepoch > prevepoch: + if (curepoch % 100) > 50: + # Collect price data + # We take an average over 50 subepochs to determine + # the price of each asset, weighting by volume to + # prevent abuse + contract.storage[0] = curepoch + i = 0 + numprop = contract.storage[1] + while i < numprop: + market = contract.storage[1001 + i * 4] + price = call(market, 2) + volume = call(market, 3) + contract.storage[1002 + i * 4] += price + contract.storage[1003 + i * 4] += volume * price + i += 1 + if (curepoch / 100) > (prevepoch / 100): + # If we are entering a new seculum, we determine the + # market with the highest total average price + best = 0 + bestmarket = 0 + besti = 0 + i = 0 + while i < numprop: + curtotprice = contract.storage[1002 + i * 4] + curvolume = contract.storage[1002 + i * 4] + curavgprice = curtotprice / curvolume + if curavgprice > best: + best = curavgprice + besti = i + bestmarket = contract.storage[1003 + i * 4] + i += 1 + # Reset the number of proposals to 0 + contract.storage[1] = 0 + # Reward the highest proposal + call(contract.storage[2], [best, 10^9, 0], 3) + # Record the winning market so we can later appropriately + # compensate the participants + contract.storage[2] = bestmarket + # The amount of ether allocated to the last round + contract.storage[7] = contract.storage[9] + # The amount of ether allocated to the next round + contract.storage[9] = contract.balance / 2 + # Make a proposal [0, address] + if msg.data[0] == 0 and curepoch % 100 < 50: + pid = contract.storage[1] + market = create('market.se') + c1 = create('subcurrency.se') + c2 = create('subcurrency.se') + call(market, [c1, c2], 2) + contract.storage[1000 + pid * 4] = msg.data[1] + contract.storage[1001 + pid * 4] = market + contract.storage[1] += 1 + # Claim ether [1, address] + # One unit of the first currency in the last round's winning + # market entitles you to a quantity of ether that was decided + # at the start of that epoch + elif msg.data[0] == 1: + first_subcurrency = call(contract.storage[2], 3) + # We ask the first subcurrency contract what the last transaction was. The + # way to make a claim is to send the amount of first currency units that + # you wish to claim with, and then immediately call this contract. For security + # it makes sense to set up a tx which sends both messages in sequence atomically + data = call(first_subcurrency, [], 0, 4) + from = data[0] + to = data[1] + value = data[2] + txid = data[3] + if txid > contract.storage[4] and to == contract.address: + send(to, contract.storage[7] * value / 10^9) + contract.storage[4] = txid + # Claim second currency [2, address] + # One unit of the second currency in the last round's winning + # market entitles you to one unit of the futarchy's master + # currency + elif msg.data[0] == 2: + second_subcurrency = call(contract.storage[2], 3) + data = call(first_subcurrency, [], 0, 4) + from = data[0] + to = data[1] + value = data[2] + txid = data[3] + if txid > contract.storage[4] and to == contract.address: + call(contract.storage[2], [to, value], 2) + contract.storage[4] = txid + # Purchase currency for ether (target releasing 10^9 units per seculum) + # Price starts off 1 eth for 10^9 units but increases hyperbolically to + # limit issuance + elif msg.data[0] == 3: + pre_ema = contract.storage[5] + post_ema = pre_ema + msg.value + pre_reserve = 10^18 / (10^9 + pre_ema / 10^9) + post_reserve = 10^18 / (10^9 + post_ema / 10^9) + call(contract.storage[2], [msg.sender, pre_reserve - post_reserve], 2) + last_sold = contract.storage[6] + contract.storage[5] = pre_ema * (100000 + last_sold - block.number) + msg.value + contract.storage[6] = block.number + # Claim all currencies as the ether miner of the current block + elif msg.data[0] == 2 and msg.sender == block.coinbase and block.number > contract.storage[8]: + i = 0 + numproposals = contract.storage[1] + while i < numproposals: + market = contract.storage[1001 + i * 3] + fc = call(market, 4) + sc = call(market, 5) + call(fc, [msg.sender, 1000], 2) + call(sc, [msg.sender, 1000], 2) + i += 1 + contract.storage[8] = block.number diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/heap.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/heap.se new file mode 100644 index 000000000..1bc442e6d --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/heap.se @@ -0,0 +1,55 @@ +# 0: size +# 1-n: elements + +init: + contract.storage[1000] = msg.sender +code: + # Only owner of the heap is allowed to modify it + if contract.storage[1000] != msg.sender: + stop + # push + if msg.data[0] == 0: + sz = contract.storage[0] + contract.storage[sz + 1] = msg.data[1] + k = sz + 1 + while k > 1: + bottom = contract.storage[k] + top = contract.storage[k/2] + if bottom < top: + contract.storage[k] = top + contract.storage[k/2] = bottom + k /= 2 + else: + k = 0 + contract.storage[0] = sz + 1 + # pop + elif msg.data[0] == 1: + sz = contract.storage[0] + if !sz: + return(0) + prevtop = contract.storage[1] + contract.storage[1] = contract.storage[sz] + contract.storage[sz] = 0 + top = contract.storage[1] + k = 1 + while k * 2 < sz: + bottom1 = contract.storage[k * 2] + bottom2 = contract.storage[k * 2 + 1] + if bottom1 < top and (bottom1 < bottom2 or k * 2 + 1 >= sz): + contract.storage[k] = bottom1 + contract.storage[k * 2] = top + k = k * 2 + elif bottom2 < top and bottom2 < bottom1 and k * 2 + 1 < sz: + contract.storage[k] = bottom2 + contract.storage[k * 2 + 1] = top + k = k * 2 + 1 + else: + k = sz + contract.storage[0] = sz - 1 + return(prevtop) + # top + elif msg.data[0] == 2: + return(contract.storage[1]) + # size + elif msg.data[0] == 3: + return(contract.storage[0]) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/market.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/market.se new file mode 100644 index 000000000..2303a0b60 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/market.se @@ -0,0 +1,117 @@ +# Creates a decentralized market between any two subcurrencies + +# Here, the first subcurrency is the base asset and the second +# subcurrency is the asset priced against the base asset. Hence, +# "buying" refers to trading the first for the second, and +# "selling" refers to trading the second for the first + +# storage 0: buy orders +# storage 1: sell orders +# storage 1000: first subcurrency +# storage 1001: last first subcurrency txid +# storage 2000: second subcurrency +# storage 2001: last second subcurrency txid +# storage 3000: current epoch +# storage 4000: price +# storage 4001: volume + +init: + # Heap for buy orders + contract.storage[0] = create('heap.se') + # Heap for sell orders + contract.storage[1] = create('heap.se') +code: + # Initialize with [ first_subcurrency, second_subcurrency ] + if !contract.storage[1000]: + contract.storage[1000] = msg.data[0] # First subcurrency + contract.storage[1001] = -1 + contract.storage[2000] = msg.data[1] # Second subcurrency + contract.storage[2001] = -1 + contract.storage[3000] = block.number / 1000 + stop + first_subcurrency = contract.storage[1000] + second_subcurrency = contract.storage[2000] + buy_heap = contract.storage[0] + sell_heap = contract.storage[1] + # This contract operates in "epochs" of 100 blocks + # At the end of each epoch, we process all orders + # simultaneously, independent of order. This algorithm + # prevents front-running, and generates a profit from + # the spread. The profit is permanently kept in the + # market (ie. destroyed), making both subcurrencies + # more valuable + + # Epoch transition code + if contract.storage[3000] < block.number / 100: + done = 0 + volume = 0 + while !done: + # Grab the top buy and sell order from each heap + topbuy = call(buy_heap, 1) + topsell = call(sell_heap, 1) + # An order is recorded in the heap as: + # Buys: (2^48 - 1 - price) * 2^208 + units of first currency * 2^160 + from + # Sells: price * 2^208 + units of second currency * 2^160 + from + buyprice = -(topbuy / 2^208) + buyfcvalue = (topbuy / 2^160) % 2^48 + buyer = topbuy % 2^160 + sellprice = topsell / 2^208 + sellscvalue = (topsell / 2^160) % 2^48 + seller = topsell % 2^160 + # Heap empty, or no more matching orders + if not topbuy or not topsell or buyprice < sellprice: + done = 1 + else: + # Add to volume counter + volume += buyfcvalue + # Calculate how much of the second currency the buyer gets, and + # how much of the first currency the seller gets + sellfcvalue = sellscvalue / buyprice + buyscvalue = buyfcvalue * sellprice + # Send the currency units along + call(second_subcurrency, [buyer, buyscvalue], 2) + call(first_subcurrency, [seller, sellfcvalue], 2) + if volume: + contract.storage[4000] = (buyprice + sellprice) / 2 + contract.storage[4001] = volume + contract.storage[3000] = block.number / 100 + # Make buy order [0, price] + if msg.data[0] == 0: + # We ask the first subcurrency contract what the last transaction was. The + # way to make a buy order is to send the amount of first currency units that + # you wish to buy with, and then immediately call this contract. For security + # it makes sense to set up a tx which sends both messages in sequence atomically + data = call(first_subcurrency, [], 0, 4) + from = data[0] + to = data[1] + value = data[2] + txid = data[3] + price = msg.data[1] + if txid > contract.storage[1001] and to == contract.address: + contract.storage[1001] = txid + # Adds the order to the heap + call(buy_heap, [0, -price * 2^208 + (value % 2^48) * 2^160 + from], 2) + # Make sell order [1, price] + elif msg.data[0] == 1: + # Same mechanics as buying + data = call(second_subcurrency, [], 0, 4) + from = data[0] + to = data[1] + value = data[2] + txid = data[3] + price = msg.data[1] + if txid > contract.storage[2001] and to == contract.address: + contract.storage[2001] = txid + call(sell_heap, [0, price * 2^208 + (value % 2^48) * 2^160 + from], 2) + # Ask for price + elif msg.data[0] == 2: + return(contract.storage[4000]) + # Ask for volume + elif msg.data[0] == 3: + return(contract.storage[1000]) + # Ask for first currency + elif msg.data[0] == 4: + return(contract.storage[2000]) + # Ask for second currency + elif msg.data[0] == 5: + return(contract.storage[4001]) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/subcurrency.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/subcurrency.se new file mode 100644 index 000000000..1501beff7 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/subcurrency.se @@ -0,0 +1,35 @@ +# Initialization +# Admin can issue and delete at will +init: + contract.storage[0] = msg.sender +code: + # If a message with one item is sent, that's a balance query + if msg.datasize == 1: + addr = msg.data[0] + return(contract.storage[addr]) + # If a message with two items [to, value] are sent, that's a transfer request + elif msg.datasize == 2: + from = msg.sender + fromvalue = contract.storage[from] + to = msg.data[0] + value = msg.data[1] + if fromvalue >= value and value > 0 and to > 4: + contract.storage[from] = fromvalue - value + contract.storage[to] += value + contract.storage[2] = from + contract.storage[3] = to + contract.storage[4] = value + contract.storage[5] += 1 + return(1) + return(0) + elif msg.datasize == 3 and msg.sender == contract.storage[0]: + # Admin can issue at will by sending a [to, value, 0] message + if msg.data[2] == 0: + contract.storage[msg.data[0]] += msg.data[1] + # Change admin [ newadmin, 0, 1 ] + # Set admin to 0 to disable administration + elif msg.data[2] == 1: + contract.storage[0] = msg.data[0] + # Fetch last transaction + else: + return([contract.storage[2], contract.storage[3], contract.storage[4], contract.storage[5]], 4) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/test.py b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/test.py new file mode 100644 index 000000000..301a4a845 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/cyberdyne/test.py @@ -0,0 +1,39 @@ +from __future__ import print_function +import pyethereum +t = pyethereum.tester +s = t.state() +# Create currencies +c1 = s.contract('subcurrency.se') +print("First currency: %s" % c1) +c2 = s.contract('subcurrency.se') +print("First currency: %s" % c2) +# Allocate units +s.send(t.k0, c1, 0, [t.a0, 1000, 0]) +s.send(t.k0, c1, 0, [t.a1, 1000, 0]) +s.send(t.k0, c2, 0, [t.a2, 1000000, 0]) +s.send(t.k0, c2, 0, [t.a3, 1000000, 0]) +print("Allocated units") +# Market +m = s.contract('market.se') +s.send(t.k0, m, 0, [c1, c2]) +# Place orders +s.send(t.k0, c1, 0, [m, 1000]) +s.send(t.k0, m, 0, [0, 1200]) +s.send(t.k1, c1, 0, [m, 1000]) +s.send(t.k1, m, 0, [0, 1400]) +s.send(t.k2, c2, 0, [m, 1000000]) +s.send(t.k2, m, 0, [1, 800]) +s.send(t.k3, c2, 0, [m, 1000000]) +s.send(t.k3, m, 0, [1, 600]) +print("Orders placed") +# Next epoch and ping +s.mine(100) +print("Mined 100") +s.send(t.k0, m, 0, []) +print("Updating") +# Check +assert s.send(t.k0, c2, 0, [t.a0]) == [800000] +assert s.send(t.k0, c2, 0, [t.a1]) == [600000] +assert s.send(t.k0, c1, 0, [t.a2]) == [833] +assert s.send(t.k0, c1, 0, [t.a3]) == [714] +print("Balance checks passed") diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/datafeed.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/datafeed.se new file mode 100644 index 000000000..4c4a56de8 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/datafeed.se @@ -0,0 +1,12 @@ +# Database updateable only by the original creator +data creator + +def init(): + self.creator = msg.sender + +def update(k, v): + if msg.sender == self.creator: + self.storage[k] = v + +def query(k): + return(self.storage[k]) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/ecrecover.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/ecrecover.se new file mode 100644 index 000000000..ce28f58c2 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/ecrecover.se @@ -0,0 +1,40 @@ +# So I looked up on Wikipedia what Jacobian form actually is, and noticed that it's +# actually a rather different and more clever construction than the naive version +# that I created. It may possible to achieve a further 20-50% savings by applying +# that version. + +extern all: [call] + +data JORDANMUL +data JORDANADD +data EXP + +def init(): + self.JORDANMUL = create('jacobian_mul.se') + self.JORDANADD = create('jacobian_add.se') + self.EXP = create('modexp.se') + +def call(h, v, r, s): + N = -432420386565659656852420866394968145599 + P = -4294968273 + h = mod(h, N) + r = mod(r, P) + s = mod(s, N) + Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 + Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 + x = r + xcubed = mulmod(mulmod(x, x, P), x, P) + beta = self.EXP.call(addmod(xcubed, 7, P), div(P + 1, 4), P) + + # Static-gascost ghetto conditional + y_is_positive = mod(v, 2) xor mod(beta, 2) + y = beta * y_is_positive + (P - beta) * (1 - y_is_positive) + + GZ = self.JORDANMUL.call(Gx, 1, Gy, 1, N - h, outsz=4) + XY = self.JORDANMUL.call(x, 1, y, 1, s, outsz=4) + COMB = self.JORDANADD.call(GZ[0], GZ[1], GZ[2], GZ[3], XY[0], XY[1], XY[2], XY[3], 1, outsz=5) + COMB[4] = self.EXP.call(r, N - 2, N) + Q = self.JORDANMUL.call(data=COMB, datasz=5, outsz=4) + ox = mulmod(Q[0], self.EXP.call(Q[1], P - 2, P), P) + oy = mulmod(Q[2], self.EXP.call(Q[3], P - 2, P), P) + return([ox, oy], 2) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/ecrecover_compiled.evm b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/ecrecover_compiled.evm new file mode 100644 index 000000000..f575fe70f --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/ecrecover_compiled.evm @@ -0,0 +1 @@ +6000607f535961071c80610013593961072f566000605f535961013d8061001359396101505661012b8061000e60003961013956600061023f5360003560001a6000141561012a5760806001602037602051151561002c576060511561002f565b60005b156100695760806080599059016000905260a052600060a051526001602060a05101526000604060a05101526001606060a051015260a051f25b6401000003d160000380608051826003846020516020510909098182600260605109836040516040510909828283098382830984858660026020510983098603866040518509088560405183098686888985604051098a038a85602051090809878689846040510909888960605183098a038a6080518509088960805183096080608059905901600090526101e052866101e051528560206101e05101528260406101e05101528160606101e05101526101e051f250505050505050505050505b5b6000f25b816000f090506000555961040680610168593961056e566000603f535961013d8061001359396101505661012b8061000e60003961013956600061023f5360003560001a6000141561012a5760806001602037602051151561002c576060511561002f565b60005b156100695760806080599059016000905260a052600060a051526001602060a05101526000604060a05101526001606060a051015260a051f25b6401000003d160000380608051826003846020516020510909098182600260605109836040516040510909828283098382830984858660026020510983098603866040518509088560405183098686888985604051098a038a85602051090809878689846040510909888960605183098a038a6080518509088960805183096080608059905901600090526101e052866101e051528560206101e05101528260406101e05101528160606101e05101526101e051f250505050505050505050505b5b6000f25b816000f0905060005561029a8061016860003961040256600061043f5360003560001a60001415610299576101006001602037602051151561002d5760605115610030565b60005b1561007657608059905901600090526101405260a051610140515260c051602061014051015260e051604061014051015261010051606061014051015261014051610120525b60a05115156100885760e0511561008b565b60005b156100d0576080599059016000905261016052602051610160515260405160206101605101526060516040610160510152608051606061016051015261016051610120525b61012051156100e157608061012051f25b6401000003d16000036000818260a0516040510983038360c051602051090814156101b1576000818260e051608051098303836101005160605109081415610175576080608080599059016000905260006101c0601f01536020516101e052604051610200526060516102205260805161024052818160816101c0601f01600060005460195a03f1508090509050f26101b0565b608060805990590160009052610280526000610280515260016020610280510152600060406102805101526001606061028051015261028051f25b5b808160405160c051098283610100516060510984038460805160e05109080981828360c0516020510984038460405160a051090883608051610100510909828283098382830984856020518309860386604051850908856040518309868760a051830988038860c0518509088760c051830988898a60405185098b038b8460205109088909898a836040510989098a8b60605183098c038c6080518509088b60805183096080608059905901600090526103e052866103e051528560206103e05101528260406103e05101528160606103e05101526103e051f2505050505050505050505050505b5b6000f25b816000f090506001556101928061058660003961071856600061013f5360003560001a600014156101915760a0600160203770014551231950b75fc4402da1732fc9bebf60000360a0510660a05260a05115606051156020511502011561007e5760806080599059016000905260c052600060c051526001602060c05101526000604060c05101526001606060c051015260c051f25b610120599059016000905260e052600060e051526000602060e05101526001604060e05101526000606060e05101526001608060e0510152600060a060e0510152600060c060e0510152600060e060e0510152600061010060e051015260e0517f80000000000000000000000000000000000000000000000000000000000000005b6000811115610187578060a0511615610165576080602083016081601f85016000600054614e20f15060205160a083015260405160c083015260605160e0830152608051610100830152608060208301610101601f85016000600154614e20f161017b565b6080602083016081601f85016000600054614e20f15b50600281049050610100565b608060208301f250505b5b6000f25b816000f0905060005559610406806107475939610b4d566000603f535961013d8061001359396101505661012b8061000e60003961013956600061023f5360003560001a6000141561012a5760806001602037602051151561002c576060511561002f565b60005b156100695760806080599059016000905260a052600060a051526001602060a05101526000604060a05101526001606060a051015260a051f25b6401000003d160000380608051826003846020516020510909098182600260605109836040516040510909828283098382830984858660026020510983098603866040518509088560405183098686888985604051098a038a85602051090809878689846040510909888960605183098a038a6080518509088960805183096080608059905901600090526101e052866101e051528560206101e05101528260406101e05101528160606101e05101526101e051f250505050505050505050505b5b6000f25b816000f0905060005561029a8061016860003961040256600061043f5360003560001a60001415610299576101006001602037602051151561002d5760605115610030565b60005b1561007657608059905901600090526101405260a051610140515260c051602061014051015260e051604061014051015261010051606061014051015261014051610120525b60a05115156100885760e0511561008b565b60005b156100d0576080599059016000905261016052602051610160515260405160206101605101526060516040610160510152608051606061016051015261016051610120525b61012051156100e157608061012051f25b6401000003d16000036000818260a0516040510983038360c051602051090814156101b1576000818260e051608051098303836101005160605109081415610175576080608080599059016000905260006101c0601f01536020516101e052604051610200526060516102205260805161024052818160816101c0601f01600060005460195a03f1508090509050f26101b0565b608060805990590160009052610280526000610280515260016020610280510152600060406102805101526001606061028051015261028051f25b5b808160405160c051098283610100516060510984038460805160e05109080981828360c0516020510984038460405160a051090883608051610100510909828283098382830984856020518309860386604051850908856040518309868760a051830988038860c0518509088760c051830988898a60405185098b038b8460205109088909898a836040510989098a8b60605183098c038c6080518509088b60805183096080608059905901600090526103e052866103e051528560206103e05101528260406103e05101528160606103e05101526103e051f2505050505050505050505050505b5b6000f25b816000f09050600155596100d080610b655939610c35566100be8061000e6000396100cc5660003560001a600014156100bd576060600160203760017f80000000000000000000000000000000000000000000000000000000000000005b60008111156100b157606051816040511615156020510a606051848509099150606051600282046040511615156020510a606051848509099150606051600482046040511615156020510a606051848509099150606051600882046040511615156020510a606051848509099150601081049050610038565b8160c052602060c0f250505b5b6000f25b816000f090506002556103d280610c4d60003961101f56600061095f5360003560001a600014156103d1576080600160203770014551231950b75fc4402da1732fc9bebf60000360a0526401000003d160000360c05260a0516020510660205260c0516060510660605260a051608051066080527f79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f8179860e0527f483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8610100526060516101205260c0516101205160c05161012051610120510909610140526000610180601f015360c051600761014051086101a0526004600160c05101046101c05260c0516101e05260206102006061610180601f01600060025460195a03f1506102005161016052600261016051066002604051061861022052610220516001036101605160c05103026102205161016051020161024052608080599059016000905260006102a0601f015360e0516102c05260016102e052610100516103005260016103205260205160a0510361034052818160a16102a0601f01600060005460195a03f150809050905061026052608080599059016000905260006103c0601f0153610120516103e052600161040052610240516104205260016104405260805161046052818160a16103c0601f01600060005460195a03f15080905090506103805260a080599059016000905260006104e0601f015361026051516105005260206102605101516105205260406102605101516105405260606102605101516105605261038051516105805260206103805101516105a05260406103805101516105c05260606103805101516105e05260016106005281816101216104e0601f01600060015460195a03f15080905090506104a0526000610640601f015360605161066052600260a051036106805260a0516106a05260206106c06061610640601f01600060025460195a03f1506106c05160806104a05101526104a05160208103805160018303608080599059016000905260008353818160a185600060005460195a03f150838552809050905090509050905090506106e05260c05160006107e0601f015360206106e051015161080052600260c051036108205260c05161084052602061086060616107e0601f01600060025460195a03f150610860516106e05151096107c05260c05160006108a0601f015360606106e05101516108c052600260c051036108e05260c05161090052602061092060616108a0601f01600060025460195a03f1506109205160406106e05101510961088052604060405990590160009052610940526107c051610940515261088051602061094051015261094051f25b5b6000f2 diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_add.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_add.se new file mode 100644 index 000000000..29dc390b2 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_add.se @@ -0,0 +1,32 @@ +extern all: [call] +data DOUBLE + +def init(): + self.DOUBLE = create('jacobian_double.se') + +def call(axn, axd, ayn, ayd, bxn, bxd, byn, byd): + if !axn and !ayn: + o = [bxn, bxd, byn, byd] + if !bxn and !byn: + o = [axn, axd, ayn, ayd] + if o: + return(o, 4) + with P = -4294968273: + if addmod(mulmod(axn, bxd, P), P - mulmod(axd, bxn, P), P) == 0: + if addmod(mulmod(ayn, byd, P), P - mulmod(ayd, byn, P), P) == 0: + return(self.DOUBLE.call(axn, axd, ayn, ayd, outsz=4), 4) + else: + return([0, 1, 0, 1], 4) + with mn = mulmod(addmod(mulmod(byn, ayd, P), P - mulmod(ayn, byd, P), P), mulmod(bxd, axd, P), P): + with md = mulmod(mulmod(byd, ayd, P), addmod(mulmod(bxn, axd, P), P - mulmod(axn, bxd, P), P), P): + with msqn = mulmod(mn, mn, P): + with msqd = mulmod(md, md, P): + with msqman = addmod(mulmod(msqn, axd, P), P - mulmod(msqd, axn, P), P): + with msqmad = mulmod(msqd, axd, P): + with xn = addmod(mulmod(msqman, bxd, P), P - mulmod(msqmad, bxn, P), P): + with xd = mulmod(msqmad, bxd, P): + with mamxn = mulmod(mn, addmod(mulmod(axn, xd, P), P - mulmod(xn, axd, P), P), P): + with mamxd = mulmod(md, mulmod(axd, xd, P), P): + with yn = addmod(mulmod(mamxn, ayd, P), P - mulmod(mamxd, ayn, P), P): + with yd = mulmod(mamxd, ayd, P): + return([xn, xd, yn, yd], 4) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_double.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_double.se new file mode 100644 index 000000000..b7d8221a6 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_double.se @@ -0,0 +1,16 @@ +def call(axn, axd, ayn, ayd): + if !axn and !ayn: + return([0, 1, 0, 1], 4) + with P = -4294968273: + # No need to add (A, 1) because A = 0 for bitcoin + with mn = mulmod(mulmod(mulmod(axn, axn, P), 3, P), ayd, P): + with md = mulmod(mulmod(axd, axd, P), mulmod(ayn, 2, P), P): + with msqn = mulmod(mn, mn, P): + with msqd = mulmod(md, md, P): + with xn = addmod(mulmod(msqn, axd, P), P - mulmod(msqd, mulmod(axn, 2, P), P), P): + with xd = mulmod(msqd, axd, P): + with mamxn = mulmod(addmod(mulmod(axn, xd, P), P - mulmod(axd, xn, P), P), mn, P): + with mamxd = mulmod(mulmod(axd, xd, P), md, P): + with yn = addmod(mulmod(mamxn, ayd, P), P - mulmod(mamxd, ayn, P), P): + with yd = mulmod(mamxd, ayd, P): + return([xn, xd, yn, yd], 4) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_mul.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_mul.se new file mode 100644 index 000000000..bf5b96bb4 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/jacobian_mul.se @@ -0,0 +1,37 @@ +# Expected gas cost +# +# def expect(n, point_at_infinity=False): +# n = n % (2**256 - 432420386565659656852420866394968145599) +# if point_at_infinity: +# return 79 +# if n == 0: +# return 34479 +# L = int(1 + math.log(n) / math.log(2)) +# H = len([x for x in b.encode(n, 2) if x == '1']) +# return 34221 + 94 * L + 343 * H + +data DOUBLE +data ADD + +def init(): + self.DOUBLE = create('jacobian_double.se') + self.ADD = create('jacobian_add.se') + +def call(axn, axd, ayn, ayd, n): + n = mod(n, -432420386565659656852420866394968145599) + if !axn * !ayn + !n: # Constant-gas version of !axn and !ayn or !n + return([0, 1, 0, 1], 4) + with o = [0, 0, 1, 0, 1, 0, 0, 0, 0]: + with b = 2 ^ 255: + while gt(b, 0): + if n & b: + ~call(20000, self.DOUBLE, 0, o + 31, 129, o + 32, 128) + o[5] = axn + o[6] = axd + o[7] = ayn + o[8] = ayd + ~call(20000, self.ADD, 0, o + 31, 257, o + 32, 128) + else: + ~call(20000, self.DOUBLE, 0, o + 31, 129, o + 32, 128) + b = div(b, 2) + return(o + 32, 4) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/modexp.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/modexp.se new file mode 100644 index 000000000..687b12a04 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/modexp.se @@ -0,0 +1,11 @@ +def call(b, e, m): + with o = 1: + with bit = 2 ^ 255: + while gt(bit, 0): + # A touch of loop unrolling for 20% efficiency gain + o = mulmod(mulmod(o, o, m), b ^ !(!(e & bit)), m) + o = mulmod(mulmod(o, o, m), b ^ !(!(e & div(bit, 2))), m) + o = mulmod(mulmod(o, o, m), b ^ !(!(e & div(bit, 4))), m) + o = mulmod(mulmod(o, o, m), b ^ !(!(e & div(bit, 8))), m) + bit = div(bit, 16) + return(o) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/substitutes.py b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/substitutes.py new file mode 100644 index 000000000..0007da0cf --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/substitutes.py @@ -0,0 +1,78 @@ +import bitcoin as b +import math +import sys + + +def signed(o): + return map(lambda x: x - 2**256 if x >= 2**255 else x, o) + + +def hamming_weight(n): + return len([x for x in b.encode(n, 2) if x == '1']) + + +def binary_length(n): + return len(b.encode(n, 2)) + + +def jacobian_mul_substitute(A, B, C, D, N): + if A == 0 and C == 0 or (N % b.N) == 0: + return {"gas": 86, "output": [0, 1, 0, 1]} + else: + output = b.jordan_multiply(((A, B), (C, D)), N) + return { + "gas": 35262 + 95 * binary_length(N % b.N) + 355 * hamming_weight(N % b.N), + "output": signed(list(output[0]) + list(output[1])) + } + + +def jacobian_add_substitute(A, B, C, D, E, F, G, H): + if A == 0 or E == 0: + gas = 149 + elif (A * F - B * E) % b.P == 0: + if (C * H - D * G) % b.P == 0: + gas = 442 + else: + gas = 177 + else: + gas = 301 + output = b.jordan_add(((A, B), (C, D)), ((E, F), (G, H))) + return { + "gas": gas, + "output": signed(list(output[0]) + list(output[1])) + } + + +def modexp_substitute(base, exp, mod): + return { + "gas": 5150, + "output": signed([pow(base, exp, mod) if mod > 0 else 0]) + } + + +def ecrecover_substitute(z, v, r, s): + P, A, B, N, Gx, Gy = b.P, b.A, b.B, b.N, b.Gx, b.Gy + x = r + beta = pow(x*x*x+A*x+B, (P + 1) / 4, P) + BETA_PREMIUM = modexp_substitute(x, (P + 1) / 4, P)["gas"] + y = beta if v % 2 ^ beta % 2 else (P - beta) + Gz = b.jordan_multiply(((Gx, 1), (Gy, 1)), (N - z) % N) + GZ_PREMIUM = jacobian_mul_substitute(Gx, 1, Gy, 1, (N - z) % N)["gas"] + XY = b.jordan_multiply(((x, 1), (y, 1)), s) + XY_PREMIUM = jacobian_mul_substitute(x, 1, y, 1, s % N)["gas"] + Qr = b.jordan_add(Gz, XY) + QR_PREMIUM = jacobian_add_substitute(Gz[0][0], Gz[0][1], Gz[1][0], Gz[1][1], + XY[0][0], XY[0][1], XY[1][0], XY[1][1] + )["gas"] + Q = b.jordan_multiply(Qr, pow(r, N - 2, N)) + Q_PREMIUM = jacobian_mul_substitute(Qr[0][0], Qr[0][1], Qr[1][0], Qr[1][1], + pow(r, N - 2, N))["gas"] + R_PREMIUM = modexp_substitute(r, N - 2, N)["gas"] + OX_PREMIUM = modexp_substitute(Q[0][1], P - 2, P)["gas"] + OY_PREMIUM = modexp_substitute(Q[1][1], P - 2, P)["gas"] + Q = b.from_jordan(Q) + return { + "gas": 991 + BETA_PREMIUM + GZ_PREMIUM + XY_PREMIUM + QR_PREMIUM + + Q_PREMIUM + R_PREMIUM + OX_PREMIUM + OY_PREMIUM, + "output": signed(Q) + } diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/test.py b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/test.py new file mode 100644 index 000000000..48d21e32f --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/ecc/test.py @@ -0,0 +1,129 @@ +import bitcoin as b +import random +import sys +import math +from pyethereum import tester as t +import substitutes +import time + +vals = [random.randrange(2**256) for i in range(12)] + +test_points = [list(p[0]) + list(p[1]) for p in + [b.jordan_multiply(((b.Gx, 1), (b.Gy, 1)), r) for r in vals]] + +G = [b.Gx, 1, b.Gy, 1] +Z = [0, 1, 0, 1] + + +def neg_point(p): + return [p[0], b.P - p[1], p[2], b.P - p[3]] + +s = t.state() +s.block.gas_limit = 10000000 +t.gas_limit = 1000000 + + +c = s.contract('modexp.se') +print "Starting modexp tests" + +for i in range(0, len(vals) - 2, 3): + o1 = substitutes.modexp_substitute(vals[i], vals[i+1], vals[i+2]) + o2 = s.profile(t.k0, c, 0, funid=0, abi=vals[i:i+3]) + #assert o1["gas"] == o2["gas"], (o1, o2) + assert o1["output"] == o2["output"], (o1, o2) + +c = s.contract('jacobian_add.se') +print "Starting addition tests" + +for i in range(2): + P = test_points[i * 2] + Q = test_points[i * 2 + 1] + NP = neg_point(P) + + o1 = substitutes.jacobian_add_substitute(*(P + Q)) + o2 = s.profile(t.k0, c, 0, funid=0, abi=P + Q) + #assert o1["gas"] == o2["gas"], (o1, o2) + assert o1["output"] == o2["output"], (o1, o2) + + o1 = substitutes.jacobian_add_substitute(*(P + NP)) + o2 = s.profile(t.k0, c, 0, funid=0, abi=P + NP) + #assert o1["gas"] == o2["gas"], (o1, o2) + assert o1["output"] == o2["output"], (o1, o2) + + o1 = substitutes.jacobian_add_substitute(*(P + P)) + o2 = s.profile(t.k0, c, 0, funid=0, abi=P + P) + #assert o1["gas"] == o2["gas"], (o1, o2) + assert o1["output"] == o2["output"], (o1, o2) + + o1 = substitutes.jacobian_add_substitute(*(P + Z)) + o2 = s.profile(t.k0, c, 0, funid=0, abi=P + Z) + #assert o1["gas"] == o2["gas"], (o1, o2) + assert o1["output"] == o2["output"], (o1, o2) + + o1 = substitutes.jacobian_add_substitute(*(Z + P)) + o2 = s.profile(t.k0, c, 0, funid=0, abi=Z + P) + #assert o1["gas"] == o2["gas"], (o1, o2) + assert o1["output"] == o2["output"], (o1, o2) + + +c = s.contract('jacobian_mul.se') +print "Starting multiplication tests" + + +mul_tests = [ + Z + [0], + Z + [vals[0]], + test_points[0] + [0], + test_points[1] + [b.N], + test_points[2] + [1], + test_points[2] + [2], + test_points[2] + [3], + test_points[2] + [4], + test_points[3] + [5], + test_points[3] + [6], + test_points[4] + [7], + test_points[4] + [2**254], + test_points[4] + [vals[1]], + test_points[4] + [vals[2]], + test_points[4] + [vals[3]], + test_points[5] + [2**256 - 1], +] + +for i, test in enumerate(mul_tests): + print 'trying mul_test %i' % i, test + o1 = substitutes.jacobian_mul_substitute(*test) + o2 = s.profile(t.k0, c, 0, funid=0, abi=test) + # assert o1["gas"] == o2["gas"], (o1, o2, test) + assert o1["output"] == o2["output"], (o1, o2, test) + +c = s.contract('ecrecover.se') +print "Starting ecrecover tests" + +for i in range(5): + print 'trying ecrecover_test', vals[i*2], vals[i*2+1] + k = vals[i*2] + h = vals[i*2+1] + V, R, S = b.ecdsa_raw_sign(b.encode(h, 256, 32), k) + aa = time.time() + o1 = substitutes.ecrecover_substitute(h, V, R, S) + print 'sub', time.time() - aa + a = time.time() + o2 = s.profile(t.k0, c, 0, funid=0, abi=[h, V, R, S]) + print time.time() - a + # assert o1["gas"] == o2["gas"], (o1, o2, h, V, R, S) + assert o1["output"] == o2["output"], (o1, o2, h, V, R, S) + +# Explicit tests + +data = [[ + 0xf007a9c78a4b2213220adaaf50c89a49d533fbefe09d52bbf9b0da55b0b90b60, + 0x1b, + 0x5228fc9e2fabfe470c32f459f4dc17ef6a0a81026e57e4d61abc3bc268fc92b5, + 0x697d4221cd7bc5943b482173de95d3114b9f54c5f37cc7f02c6910c6dd8bd107 +]] + +for datum in data: + o1 = substitutes.ecrecover_substitute(*datum) + o2 = s.profile(t.k0, c, 0, funid=0, abi=datum) + #assert o1["gas"] == o2["gas"], (o1, o2, datum) + assert o1["output"] == o2["output"], (o1, o2, datum) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/channel.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/channel.se new file mode 100644 index 000000000..733f4a95b --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/channel.se @@ -0,0 +1,45 @@ +if msg.data[0] == 0: + new_id = contract.storage[-1] + # store [from, to, value, maxvalue, timeout] in contract storage + contract.storage[new_id] = msg.sender + contract.storage[new_id + 1] = msg.data[1] + contract.storage[new_id + 2] = 0 + contract.storage[new_id + 3] = msg.value + contract.storage[new_id + 4] = 2^254 + # increment next id + contract.storage[-1] = new_id + 10 + # return id of this channel + return(new_id) + +# Increase payment on channel: [1, id, value, v, r, s] +elif msg.data[0] == 1: + # Ecrecover native extension; will be a different address in testnet and live + ecrecover = 0x46a8d0b21b1336d83b06829f568d7450df36883f + # Message data parameters + id = msg.data[1] % 2^160 + value = msg.data[2] + # Determine sender from signature + h = sha3([id, value], 2) + sender = call(ecrecover, [h, msg.data[3], msg.data[4], msg.data[5]], 4) + # Check sender matches and new value is greater than old + if sender == contract.storage[id]: + if value > contract.storage[id + 2] and value <= contract.storage[id + 3]: + # Update channel, increasing value and setting timeout + contract.storage[id + 2] = value + contract.storage[id + 4] = block.number + 1000 + +# Cash out channel: [2, id] +elif msg.data[0] == 2: + id = msg.data[1] % 2^160 + # Check if timeout has run out + if block.number >= contract.storage[id + 3]: + # Send funds + send(contract.storage[id + 1], contract.storage[id + 2]) + # Send refund + send(contract.storage[id], contract.storage[id + 3] - contract.storage[id + 2]) + # Clear storage + contract.storage[id] = 0 + contract.storage[id + 1] = 0 + contract.storage[id + 2] = 0 + contract.storage[id + 3] = 0 + contract.storage[id + 4] = 0 diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/map.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/map.se new file mode 100644 index 000000000..768dfb9fc --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/map.se @@ -0,0 +1,19 @@ +# An implementation of a contract for storing a key/value binding +init: + # Set owner + contract.storage[0] = msg.sender +code: + # Check ownership + if msg.sender == contract.storage[0]: + # Get: returns (found, val) + if msg.data[0] == 0: + s = sha3(msg.data[1]) + return([contract.storage[s], contract.storage[s+1]], 2) + # Set: sets map[k] = v + elif msg.data[0] == 1: + s = sha3(msg.data[1]) + contract.storage[s] = 1 + contract.storage[s + 1] = msg.data[2] + # Suicide + elif msg.data[2] == 1: + suicide(0) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/multiforward.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/multiforward.se new file mode 100644 index 000000000..577794d97 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/multiforward.se @@ -0,0 +1,14 @@ +init: + contract.storage[0] = msg.sender +code: + if msg.sender != contract.storage[0]: + stop + i = 0 + while i < ~calldatasize(): + to = ~calldataload(i) + value = ~calldataload(i+20) / 256^12 + datasize = ~calldataload(i+32) / 256^30 + data = alloc(datasize) + ~calldatacopy(data, i+34, datasize) + ~call(tx.gas - 25, to, value, data, datasize, 0, 0) + i += 34 + datasize diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/shadowchain.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/shadowchain.se new file mode 100644 index 000000000..1e466a355 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/eth15/shadowchain.se @@ -0,0 +1,166 @@ +# Exists in state: +# (i) last committed block +# (ii) chain of uncommitted blocks (linear only) +# (iii) transactions, each tx with an associated block number +# +# Uncommitted block = +# [ numtxs, numkvs, tx1 (N words), tx2 (N words) ..., [k1, v1], [k2, v2], [k3, v3] ... ] +# +# Block checking process +# +# Suppose last committed state is m +# Last uncommitted state is n +# Contested block is b +# +# 1. Temporarily apply all state transitions from +# m to b +# 2. Run code, get list of changes +# 3. Check is list of changes matches deltas +# * if yes, do nothing +# * if no, set last uncommitted state to pre-b +# +# Storage variables: +# +# Last committed block: 0 +# Last uncommitted block: 1 +# Contract holding code: 2 +# Uncommitted map: 3 +# Transaction length (parameter): 4 +# Block b: 2^160 + b * 2^40: +# + 1: submission blknum +# + 2: submitter +# + 3: data in uncommitted block format above +# Last committed storage: +# sha3(k): index k + +# Initialize: [0, c, txlength], set address of the code-holding contract and the transaction +# length +if not contract.storage[2]: + contract.storage[2] = msg.data[1] + contract.storage[4] = msg.data[2] + stop + +# Sequentially commit all uncommitted blocks that are more than 1000 mainchain-blocks old +last_committed_block = contract.storage[0] +last_uncommitted_block = contract.storage[1] +lcb_storage_index = 2^160 + last_committed_block * 2^40 +while contract.storage[lcb_storage_index + 1] < block.number - 1000 and last_committed_block < last_uncommitted_block: + kvpairs = contract.storage[lcb_storage_index] + i = 0 + while i < kvpairs: + k = contract.storage[lcb_storage_index + 3 + i * 2] + v = contract.storage[lcb_storage_index + 4 + i * 2] + contract.storage[sha3(k)] = v + i += 1 + last_committed_block += 1 + lcb_storage_index += 2^40 +contract.storage[0] = last_committed_block + + +# Propose block: [ 0, block number, data in block format above ... ] +if msg.data[0] == 0: + blknumber = msg.data[1] + # Block number must be correct + if blknumber != contract.storage[1]: + stop + # Deposit requirement + if msg.value < 10^19: + stop + # Store the proposal in storage as + # [ 0, main-chain block number, sender, block data...] + start_index = 2^160 + blknumber * 2^40 + numkvs = (msg.datasize - 2) / 2 + contract.storage[start_index + 1] = block.number + 1ontract.storage[start_index + 2] = msg.sender + i = 0 + while i < msg.datasize - 2: + contract.storage[start_index + 3 + i] = msg.data[2 + i] + i += 1 + contract.storage[1] = blknumber + 1 + +# Challenge block: [ 1, b ] +elif msg.data[0] == 1: + blknumber = msg.data[1] + txwidth = contract.storage[4] + last_uncommitted_block = contract.storage[1] + last_committed_block = contract.storage[0] + # Cannot challenge nonexistent or committed blocks + if blknumber <= last_uncommitted_block or blknumber > last_committed_block: + stop + # Create a contract to serve as a map that maintains keys and values + # temporarily + tempstore = create('map.se') + contract.storage[3] = tempstore + # Unquestioningly apply the state transitions from the last committed block + # up to b + b = last_committed_block + cur_storage_index = 2^160 + last_committed_block * 2^40 + while b < blknumber: + numtxs = contract.storage[cur_storage_index + 3] + numkvs = contract.storage[cur_storage_index + 4] + kv0index = cur_storage_index + 5 + numtxs * txwidth + i = 0 + while i < numkvs: + k = contract.storage[kv0index + i * 2] + v = contract.storage[kx0index + i * 2 + 1] + call(tempstore, [1, k, v], 3) + i += 1 + b += 1 + cur_storage_index += 2^40 + # Run the actual code, and see what state transitions it outputs + # The way that the code is expected to work is to: + # + # (1) take as input the list of transactions (the contract should + # use msg.datasize to determine how many txs there are, and it should + # be aware of the value of txwidth) + # (2) call this contract with [2, k] to read current state data + # (3) call this contract with [3, k, v] to write current state data + # (4) return as output a list of all state transitions that it made + # in the form [kvcount, k1, v1, k2, v2 ... ] + # + # The reason for separating (2) from (3) is that sometimes the state + # transition may end up changing a given key many times, and we don't + # need to inefficiently store that in storage + numkvs = contract.storage[cur_storage_index + 3] + numtxs = contract.storage[cur_storage_index + 4] + # Populate input array + inpwidth = numtxs * txwidth + inp = array(inpwidth) + i = 0 + while i < inpwidth: + inp[i] = contract.storage[cur_storage_index + 5 + i] + i += 1 + out = call(contract.storage[2], inp, inpwidth, numkvs * 2 + 1) + # Check that the number of state transitions is the same + if out[0] != kvcount: + send(msg.sender, 10^19) + contract.storage[0] = last_committed_block + stop + kv0index = cur_storage_index + 5 + numtxs * txwidth + i = 0 + while i < kvcount: + # Check that each individual state transition matches + k = contract.storage[kv0index + i * 2 + 1] + v = contract.storage[kv0index + i * 2 + 2] + if k != out[i * 2 + 1] or v != out[i * 2 + 2]: + send(msg.sender, 10^19) + contract.storage[0] = last_committed_block + stop + i += 1 + # Suicide tempstore + call(tempstore, 2) + + +# Read data [2, k] +elif msg.data[0] == 2: + tempstore = contract.storage[3] + o = call(tempstore, [0, msg.data[1]], 2, 2) + if o[0]: + return(o[1]) + else: + return contract.storage[sha3(msg.data[1])] + +# Write data [3, k, v] +elif msg.data[0] == 3: + tempstore = contract.storage[3] + call(tempstore, [1, msg.data[1], msg.data[2]], 3, 2) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/fixedpoint.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/fixedpoint.se new file mode 100644 index 000000000..a8073c685 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/fixedpoint.se @@ -0,0 +1,31 @@ +type f: [a, b, c, d, e] + +macro f($a) + f($b): + f(add($a, $b)) + +macro f($a) - f($b): + f(sub($a, $b)) + +macro f($a) * f($b): + f(mul($a, $b) / 10000) + +macro f($a) / f($b): + f(sdiv($a * 10000, $b)) + +macro f($a) % f($b): + f(smod($a, $b)) + +macro f($v) = f($w): + $v = $w + +macro unfify(f($a)): + $a / 10000 + +macro fify($a): + f($a * 10000) + +a = fify(5) +b = fify(2) +c = a / b +e = c + (a / b) +return(unfify(e)) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/long_integer_macros.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/long_integer_macros.se new file mode 100644 index 000000000..58cdce6ab --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/long_integer_macros.se @@ -0,0 +1,116 @@ +macro smin($a, $b): + with $1 = $a: + with $2 = $b: + if(slt($1, $2), $1, $2) + +macro smax($a, $b): + with $1 = $a: + with $2 = $b: + if(slt($1, $2), $2, $1) + +def omul(x, y): + o = expose(mklong(x) * mklong(y)) + return(slice(o, 1), o[0]+1) + +def oadd(x, y): + o = expose(mklong(x) + mklong(y)) + return(slice(o, 1), o[0]+1) + +def osub(x, y): + o = expose(mklong(x) - mklong(y)) + return(slice(o, 1), o[0]+1) + +def odiv(x, y): + o = expose(mklong(x) / mklong(y)) + return(slice(o, 1), o[0]+1) + +def comb(a:a, b:a, sign): + sz = smax(a[0], b[0]) + msz = smin(a[0], b[0]) + c = array(sz + 2) + c[0] = sz + i = 0 + carry = 0 + while i < msz: + m = a[i + 1] + sign * b[i + 1] + carry + c[i + 1] = mod(m + 2^127, 2^128) - 2^127 + carry = (div(m + 2^127, 2^128) + 2^127) % 2^128 - 2^127 + i += 1 + u = if(a[0] > msz, a, b) + s = if(a[0] > msz, 1, sign) + while i < sz: + m = s * u[i + 1] + carry + c[i + 1] = mod(m + 2^127, 2^128) - 2^127 + carry = (div(m + 2^127, 2^128) + 2^127) % 2^128 - 2^127 + i += 1 + if carry: + c[0] += 1 + c[sz + 1] = carry + return(c, c[0]+1) + +def mul(a:a, b:a): + c = array(a[0] + b[0] + 2) + c[0] = a[0] + b[0] + i = 0 + while i < a[0]: + j = 0 + carry = 0 + while j < b[0]: + m = c[i + j + 1] + a[i + 1] * b[j + 1] + carry + c[i + j + 1] = mod(m + 2^127, 2^128) - 2^127 + carry = (div(m + 2^127, 2^128) + 2^127) % 2^128 - 2^127 + j += 1 + if carry: + c[0] = a[0] + b[0] + 1 + c[i + j + 1] += carry + i += 1 + return(c, c[0]+1) + +macro long($a) + long($b): + long(self.comb($a:$a[0]+1, $b:$b[0]+1, 1, outsz=$a[0]+$b[0]+2)) + +macro long($a) - long($b): + long(self.comb($a:$a[0]+1, $b:$b[0]+1, -1, outsz=$a[0]+$b[0]+2)) + +macro long($a) * long($b): + long(self.mul($a:$a[0]+1, $b:$b[0]+1, outsz=$a[0]+$b[0]+2)) + +macro long($a) / long($b): + long(self.div($a:$a[0]+1, $b:$b[0]+1, outsz=$a[0]+$b[0]+2)) + +macro mulexpand(long($a), $k, $m): + long: + with $c = array($a[0]+k+2): + $c[0] = $a[0]+$k + with i = 0: + while i < $a[0]: + v = $a[i+1] * $m + $c[i+$k+1] + $c[i+$k+1] = mod(v + 2^127, 2^128) - 2^127 + $c[i+$k+2] = div(v + 2^127, 2^128) + i += 1 + $c + +def div(a:a, b:a): + asz = a[0] + bsz = b[0] + while b[bsz] == 0 and bsz > 0: + bsz -= 1 + c = array(asz+2) + c[0] = asz+1 + while 1: + while a[asz] == 0 and asz > 0: + asz -= 1 + if asz < bsz: + return(c, c[0]+1) + sub = expose(mulexpand(long(b), asz - bsz, a[asz] / b[bsz])) + c[asz - bsz+1] = a[asz] / b[bsz] + a = expose(long(a) - long(sub)) + a[asz-1] += 2^128 * a[asz] + a[asz] = 0 + +macro mklong($i): + long([2, mod($i + 2^127, 2^128) - 2^127, div($i + 2^127, 2^128)]) + +macro expose(long($i)): + $i + diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/mul2.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/mul2.se new file mode 100644 index 000000000..65adff1e6 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/mul2.se @@ -0,0 +1,2 @@ +def double(v): + return(v*2) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/mutuala.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/mutuala.se new file mode 100644 index 000000000..3efb0edeb --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/mutuala.se @@ -0,0 +1,187 @@ +# mutuala - subcurrency + +# We want to issue a currency that reduces in value as you store it through negative interest. +# That negative interest would be stored in a commons account. It's like the p2p version of a +# capital tax + +# the same things goes for transactions - you pay as you use the currency. However, the more +# you pay, the more you get to say about what the tax is used for + +# each participant can propose a recipient for a payout to be made out of the commons account, +# others can vote on it by awarding it tax_credits. + +# TODO should proposal have expiration timestamp?, after which the tax_credits are refunded +# TODO multiple proposals can take more credits that available in the Commons, how to handle this +# TODO how to handle lost accounts, after which no longer possible to get 2/3 majority + +shared: + COMMONS = 42 + ADMIN = 666 + CAPITAL_TAX_PER_DAY = 7305 # 5% per year + PAYMENT_TAX = 20 # 5% + + ACCOUNT_LIST_OFFSET = 2^160 + ACCOUNT_MAP_OFFSET = 2^161 + PROPOSAL_LIST_OFFSET = 2^162 + PROPOSAL_MAP_OFFSET = 2^163 + +init: + contract.storage[ADMIN] = msg.sender + contract.storage[ACCOUNT_LIST_OFFSET - 1] = 1 + contract.storage[ACCOUNT_LIST_OFFSET] = msg.sender + contract.storage[ACCOUNT_MAP_OFFSET + msg.sender] = 10^12 + contract.storage[ACCOUNT_MAP_OFFSET + msg.sender + 1] = block.timestamp + +# contract.storage[COMMONS] = balance commons + +# contract.storage[ACCOUNT_LIST_OFFSET - 1] = number of accounts +# contract.storage[ACCOUNT_LIST_OFFSET + n] = account n + +# contract.storage[PROPOSAL_LIST_OFFSET - 1] contains the number of proposals +# contract.storage[PROPOSAL_LIST_OFFSET + n] = proposal n + +# per account: +# contract.storage[ACCOUNT_MAP_OFFSET + account] = balance +# contract.storage[ACCOUNT_MAP_OFFSET + account+1] = timestamp_last_transaction +# contract.storage[ACCOUNT_MAP_OFFSET + account+2] = tax_credits + +# per proposal: +# contract.storage[PROPOSAL_MAP_OFFSET + proposal_id] = recipient +# contract.storage[PROPOSAL_MAP_OFFSET + proposal_id+1] = amount +# contract.storage[PROPOSAL_MAP_OFFSET + proposal_id+2] = total vote credits + +code: + if msg.data[0] == "suicide" and msg.sender == contract.storage[ADMIN]: + suicide(msg.sender) + + elif msg.data[0] == "balance": + addr = msg.data[1] + return(contract.storage[ACCOUNT_MAP_OFFSET + addr]) + + elif msg.data[0] == "pay": + from = msg.sender + fromvalue = contract.storage[ACCOUNT_MAP_OFFSET + from] + to = msg.data[1] + if to == 0 or to >= 2^160: + return([0, "invalid address"], 2) + value = msg.data[2] + tax = value / PAYMENT_TAX + + if fromvalue >= value + tax: + contract.storage[ACCOUNT_MAP_OFFSET + from] = fromvalue - (value + tax) + contract.storage[ACCOUNT_MAP_OFFSET + to] += value + # tax + contract.storage[COMMONS] += tax + contract.storage[ACCOUNT_MAP_OFFSET + from + 2] += tax + + # check timestamp field to see if target account exists + if contract.storage[ACCOUNT_MAP_OFFSET + to + 1] == 0: + # register new account + nr_accounts = contract.storage[ACCOUNT_LIST_OFFSET - 1] + contract.storage[ACCOUNT_LIST_OFFSET + nr_accounts] = to + contract.storage[ACCOUNT_LIST_OFFSET - 1] += 1 + contract.storage[ACCOUNT_MAP_OFFSET + to + 1] = block.timestamp + + return(1) + else: + return([0, "insufficient balance"], 2) + + elif msg.data[0] == "hash": + proposal_id = sha3(msg.data[1]) + return(proposal_id) + + elif msg.data[0] == "propose": + from = msg.sender + # check if sender has an account and has tax credits + if contract.storage[ACCOUNT_MAP_OFFSET + from + 2] == 0: + return([0, "sender has no tax credits"], 2) + + proposal_id = sha3(msg.data[1]) + # check if proposal doesn't already exist + if contract.storage[PROPOSAL_MAP_OFFSET + proposal_id]: + return([0, "proposal already exists"]) + + to = msg.data[2] + # check if recipient is a valid address and has an account (with timestamp) + if to == 0 or to >= 2^160: + return([0, "invalid address"], 2) + if contract.storage[ACCOUNT_MAP_OFFSET + to + 1] == 0: + return([0, "invalid to account"], 2) + + value = msg.data[3] + # check if there is enough money in the commons account + if value > contract.storage[COMMONS]: + return([0, "not enough credits in commons"], 2) + + # record proposal in list + nr_proposals = contract.storage[PROPOSAL_LIST_OFFSET - 1] + contract.storage[PROPOSAL_LIST_OFFSET + nr_proposals] = proposal_id + contract.storage[PROPOSAL_LIST_OFFSET - 1] += 1 + + # record proposal in map + contract.storage[PROPOSAL_MAP_OFFSET + proposal_id] = to + contract.storage[PROPOSAL_MAP_OFFSET + proposal_id + 1] = value + + return(proposal_id) + + elif msg.data[0] == "vote": + from = msg.sender + proposal_id = sha3(msg.data[1]) + value = msg.data[2] + # check if sender has an account and has tax credits + if value < contract.storage[ACCOUNT_MAP_OFFSET + from + 2]: + return([0, "sender doesn't have enough tax credits"], 2) + + # check if proposal exist + if contract.storage[PROPOSAL_MAP_OFFSET + proposal_id] == 0: + return([0, "proposal doesn't exist"], 2) + + # increase votes + contract.storage[PROPOSAL_MAP_OFFSET + proposal_id + 2] += value + # withdraw tax credits + contract.storage[ACCOUNT_MAP_OFFSET + from + 2] -= value + + # did we reach 2/3 threshold? + if contract.storage[PROPOSAL_MAP_OFFSET + proposal_id + 2] >= contract.storage[COMMONS] * 2 / 3: + # got majority + to = contract.storage[PROPOSAL_MAP_OFFSET + proposal_id] + amount = contract.storage[PROPOSAL_MAP_OFFSET + proposal_id + 1] + + # adjust balances + contract.storage[ACCOUNT_MAP_OFFSET + to] += amount + contract.storage[COMMONS] -= amount + + # reset proposal + contract.storage[PROPOSAL_MAP_OFFSET + proposal_id] = 0 + contract.storage[PROPOSAL_MAP_OFFSET + proposal_id + 1] = 0 + contract.storage[PROPOSAL_MAP_OFFSET + proposal_id + 2] = 0 + return(1) + + return(proposal_id) + + elif msg.data[0] == "tick": + nr_accounts = contract.storage[ACCOUNT_LIST_OFFSET - 1] + account_idx = 0 + tax_paid = 0 + # process all accounts and see if they have to pay their daily capital tax + while account_idx < nr_accounts: + cur_account = contract.storage[ACCOUNT_LIST_OFFSET + account_idx] + last_timestamp = contract.storage[ACCOUNT_MAP_OFFSET + cur_account + 1] + time_diff = block.timestamp - last_timestamp + if time_diff >= 86400: + tax_days = time_diff / 86400 + balance = contract.storage[ACCOUNT_MAP_OFFSET + cur_account] + tax = tax_days * (balance / CAPITAL_TAX_PER_DAY) + if tax > 0: + # charge capital tax, but give tax credits in return + contract.storage[ACCOUNT_MAP_OFFSET + cur_account] -= tax + contract.storage[ACCOUNT_MAP_OFFSET + cur_account + 1] += tax_days * 86400 + contract.storage[ACCOUNT_MAP_OFFSET + cur_account + 2] += tax + + contract.storage[COMMONS] += tax + tax_paid += 1 + account_idx += 1 + return(tax_paid) # how many accounts did we charge tax on + + else: + return([0, "unknown command"], 2) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/namecoin.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/namecoin.se new file mode 100644 index 000000000..11d6274ae --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/namecoin.se @@ -0,0 +1,7 @@ +def register(k, v): + if !self.storage[k]: # Is the key not yet taken? + # Then take it! + self.storage[k] = v + return(1) + else: + return(0) // Otherwise do nothing diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/peano.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/peano.se new file mode 100644 index 000000000..979854444 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/peano.se @@ -0,0 +1,43 @@ +macro padd($x, psuc($y)): + psuc(padd($x, $y)) + +macro padd($x, z()): + $x + +macro dec(psuc($x)): + dec($x) + 1 + +macro dec(z()): + 0 + +macro pmul($x, z()): + z() + +macro pmul($x, psuc($y)): + padd(pmul($x, $y), $x) + +macro pexp($x, z()): + one() + +macro pexp($x, psuc($y)): + pmul($x, pexp($x, $y)) + +macro fac(z()): + one() + +macro fac(psuc($x)): + pmul(psuc($x), fac($x)) + +macro one(): + psuc(z()) + +macro two(): + psuc(psuc(z())) + +macro three(): + psuc(psuc(psuc(z()))) + +macro five(): + padd(three(), two()) + +return([dec(pmul(three(), pmul(three(), three()))), dec(fac(five()))], 2) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/returnten.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/returnten.se new file mode 100644 index 000000000..7969c9eb8 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/returnten.se @@ -0,0 +1,4 @@ +extern mul2: [double] + +x = create("mul2.se") +return(x.double(5)) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/quicksort.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/quicksort.se new file mode 100644 index 000000000..be5d97fc7 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/quicksort.se @@ -0,0 +1,33 @@ +def kall(): + argcount = ~calldatasize() / 32 + if argcount == 1: + return(~calldataload(1)) + + args = array(argcount) + ~calldatacopy(args, 1, argcount * 32) + low = array(argcount) + lsz = 0 + high = array(argcount) + hsz = 0 + i = 1 + while i < argcount: + if args[i] < args[0]: + low[lsz] = args[i] + lsz += 1 + else: + high[hsz] = args[i] + hsz += 1 + i += 1 + low = self.kall(data=low, datasz=lsz, outsz=lsz) + high = self.kall(data=high, datasz=hsz, outsz=hsz) + o = array(argcount) + i = 0 + while i < lsz: + o[i] = low[i] + i += 1 + o[lsz] = args[0] + j = 0 + while j < hsz: + o[lsz + 1 + j] = high[j] + j += 1 + return(o, argcount) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/quicksort_pairs.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/quicksort_pairs.se new file mode 100644 index 000000000..0e603a238 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/quicksort_pairs.se @@ -0,0 +1,46 @@ +# Quicksort pairs +# eg. input of the form [ 30, 1, 90, 2, 70, 3, 50, 4] +# outputs [ 30, 1, 50, 4, 70, 3, 90, 2 ] +# +# Note: this can be used as a generalized sorting algorithm: +# map every object to [ key, ref ] where `ref` is the index +# in memory to all of the properties and `key` is the key to +# sort by + + +def kall(): + argcount = ~calldatasize() / 64 + if argcount == 1: + return([~calldataload(1), ~calldataload(33)], 2) + + args = array(argcount * 2) + ~calldatacopy(args, 1, argcount * 64) + low = array(argcount * 2) + lsz = 0 + high = array(argcount * 2) + hsz = 0 + i = 2 + while i < argcount * 2: + if args[i] < args[0]: + low[lsz] = args[i] + low[lsz + 1] = args[i + 1] + lsz += 2 + else: + high[hsz] = args[i] + high[hsz + 1] = args[i + 1] + hsz += 2 + i = i + 2 + low = self.kall(data=low, datasz=lsz, outsz=lsz) + high = self.kall(data=high, datasz=hsz, outsz=hsz) + o = array(argcount * 2) + i = 0 + while i < lsz: + o[i] = low[i] + i += 1 + o[lsz] = args[0] + o[lsz + 1] = args[1] + j = 0 + while j < hsz: + o[lsz + 2 + j] = high[j] + j += 1 + return(o, argcount * 2) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/schellingcoin.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/schellingcoin.se new file mode 100644 index 000000000..a7d7da9c5 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/schellingcoin.se @@ -0,0 +1,94 @@ +# SchellingCoin implementation +# +# Epoch length: 100 blocks +# Target savings depletion rate: 0.1% per epoch + +data epoch +data hashes_submitted +data output +data quicksort_pairs +data accounts[2^160] +data submissions[2^80](hash, deposit, address, value) +extern any: [call] + + +def init(): + self.epoch = block.number / 100 + self.quicksort_pairs = create('quicksort_pairs.se') + +def any(): + if block.number / 100 > epoch: + # Sort all values submitted + N = self.hashes_submitted + o = array(N * 2) + i = 0 + j = 0 + while i < N: + v = self.submissions[i].value + if v: + o[j] = v + o[j + 1] = i + j += 2 + i += 1 + values = self.quicksort_pairs.call(data=o, datasz=j, outsz=j) + + # Calculate total deposit, refund non-submitters and + # cleanup + + deposits = array(j / 2) + addresses = array(j / 2) + + i = 0 + total_deposit = 0 + while i < j / 2: + base_index = HASHES + values[i * 2 + 1] * 3 + deposits[i] = self.submissions[i].deposit + addresses[i] = self.submissions[i].address + if self.submissions[values[i * 2 + 1]].value: + total_deposit += deposits[i] + else: + send(addresses[i], deposits[i] * 999 / 1000) + i += 1 + + inverse_profit_ratio = total_deposit / (contract.balance / 1000) + 1 + + # Reward everyone + i = 0 + running_deposit_sum = 0 + halfway_passed = 0 + while i < j / 2: + new_deposit_sum = running_deposit_sum + deposits[i] + if new_deposit_sum > total_deposit / 4 and running_deposit_sum < total_deposit * 3 / 4: + send(addresses[i], deposits[i] + deposits[i] / inverse_profit_ratio * 2) + else: + send(addresses[i], deposits[i] - deposits[i] / inverse_profit_ratio) + + if not halfway_passed and new_deposit_sum > total_deposit / 2: + self.output = self.submissions[i].value + halfway_passed = 1 + self.submissions[i].value = 0 + running_deposit_sum = new_deposit_sum + i += 1 + self.epoch = block.number / 100 + self.hashes_submitted = 0 + +def submit_hash(h): + if block.number % 100 < 50: + cur = self.hashes_submitted + pos = HASHES + cur * 3 + self.submissions[cur].hash = h + self.submissions[cur].deposit = msg.value + self.submissions[cur].address = msg.sender + self.hashes_submitted = cur + 1 + return(cur) + +def submit_value(index, v): + if sha3([msg.sender, v], 2) == self.submissions[index].hash: + self.submissions[index].value = v + return(1) + +def request_balance(): + return(contract.balance) + +def request_output(): + return(self.output) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/schellingdollar.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/schellingdollar.se new file mode 100644 index 000000000..a34f42ce2 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellingcoin/schellingdollar.se @@ -0,0 +1,171 @@ +# Hedged zero-supply dollar implementation +# Uses SchellingCoin as price-determining backend +# +# Stored variables: +# +# 0: Schelling coin contract +# 1: Last epoch +# 2: Genesis block of contract +# 3: USD exposure +# 4: ETH exposure +# 5: Cached price +# 6: Last interest rate +# 2^160 + k: interest rate accumulator at k epochs +# 2^161 + ADDR * 3: eth-balance of a particular address +# 2^161 + ADDR * 3 + 1: usd-balance of a particular address +# 2^161 + ADDR * 3 + 1: last accessed epoch of a particular address +# +# Transaction types: +# +# [1, to, val]: send ETH +# [2, to, val]: send USD +# [3, wei_amount]: convert ETH to USD +# [4, usd_amount]: converts USD to ETH +# [5]: deposit +# [6, amount]: withdraw +# [7]: my balance query +# [7, acct]: balance query for any acct +# [8]: global state query +# [9]: liquidation test any account +# +# The purpose of the contract is to serve as a sort of cryptographic +# bank account where users can store both ETH and USD. ETH must be +# stored in zero or positive quantities, but USD balances can be +# positive or negative. If the USD balance is negative, the invariant +# usdbal * 10 >= ethbal * 9 must be satisfied; if any account falls +# below this value, then that account's balances are zeroed. Note +# that there is a 2% bounty to ping the app if an account does go +# below zero; one weakness is that if no one does ping then it is +# quite possible for accounts to go negative-net-worth, then zero +# themselves out, draining the reserves of the "bank" and potentially +# bankrupting it. A 0.1% fee on ETH <-> USD trade is charged to +# minimize this risk. Additionally, the bank itself will inevitably +# end up with positive or negative USD exposure; to mitigate this, +# it automatically updates interest rates on USD to keep exposure +# near zero. + +data schelling_coin +data last_epoch +data starting_block +data usd_exposure +data eth_exposure +data price +data last_interest_rate +data interest_rate_accum[2^50] +data accounts[2^160](eth, usd, last_epoch) + +extern sc: [submit_hash, submit_value, request_balance, request_output] + +def init(): + self.schelling_coin = create('schellingcoin.se') + self.price = self.schelling_coin.request_output() + self.interest_rate_accum[0] = 10^18 + self.starting_block = block.number + +def any(): + sender = msg.sender + epoch = (block.number - self.starting_block) / 100 + last_epoch = self.last_epoch + usdprice = self.price + + # Update contract epochs + if epoch > last_epoch: + delta = epoch - last_epoch + last_interest_rate = self.last_interest_rate + usd_exposure - self.usd_exposure + last_accum = self.interest_rate_accum[last_epoch] + + if usd_exposure < 0: + self.last_interest_rate = last_interest_rate - 10000 * delta + elif usd_exposure > 0: + self.last_interest_rate = last_interest_rate + 10000 * delta + + self.interest_rate_accum[epoch] = last_accum + last_accum * last_interest_rate * delta / 10^9 + + # Proceeds go to support the SchellingCoin feeding it price data, ultimately providing the depositors + # of the SchellingCoin an interest rate + bal = max(self.balance - self.eth_exposure, 0) / 10000 + usdprice = self.schelling_coin.request_output() + self.price = usdprice + self.last_epoch = epoch + + ethbal = self.accounts[msg.sender].eth + usdbal = self.accounts[msg.sender].usd + + # Apply interest rates to sender and liquidation-test self + if msg.sender != self: + self.ping(self) + +def send_eth(to, value): + if value > 0 and value <= ethbal and usdbal * usdprice * 2 + (ethbal - value) >= 0: + self.accounts[msg.sender].eth = ethbal - value + self.ping(to) + self.accounts[to].eth += value + return(1) + +def send_usd(to, value): + if value > 0 and value <= usdbal and (usdbal - value) * usdprice * 2 + ethbal >= 0: + self.accounts[msg.sender].usd = usdbal - value + self.ping(to) + self.accounts[to].usd += value + return(1) + +def convert_to_eth(usdvalue): + ethplus = usdvalue * usdprice * 999 / 1000 + if usdvalue > 0 and (usdbal - usdvalue) * usdprice * 2 + (ethbal + ethplus) >= 0: + self.accounts[msg.sender].eth = ethbal + ethplus + self.accounts[msg.sender].usd = usdbal - usdvalue + self.eth_exposure += ethplus + self.usd_exposure -= usdvalue + return([ethbal + ethplus, usdbal - usdvalue], 2) + +def convert_to_usd(ethvalue): + usdplus = ethvalue / usdprice * 999 / 1000 + if ethvalue > 0 and (usdbal + usdplus) * usdprice * 2 + (ethbal - ethvalue) >= 0: + self.accounts[msg.sender].eth = ethbal - ethvalue + self.accounts[msg.sender].usd = usdbal + usdplus + self.eth_exposure -= ethvalue + self.usd_exposure += usdplus + return([ethbal - ethvalue, usdbal + usdplus], 2) + +def deposit(): + self.accounts[msg.sender].eth = ethbal + msg.value + self.eth_exposure += msg.value + return(ethbal + msg.value) + +def withdraw(value): + if value > 0 and value <= ethbal and usdbal * usdprice * 2 + (ethbal - value) >= 0: + self.accounts[msg.sender].eth -= value + self.eth_exposure -= value + return(ethbal - value) + +def balance(acct): + self.ping(acct) + return([self.accounts[acct].eth, self.accounts[acct].usd], 2) + +def global_state_query(acct): + interest = self.last_interest_rate + usd_exposure = self.usd_exposure + eth_exposure = self.eth_exposure + eth_balance = self.balance + return([epoch, usdprice, interest, usd_exposure, eth_exposure, eth_balance], 6) + +def ping(acct): + account_last_epoch = self.accounts[acct].last_epoch + if account_last_epoch != epoch: + cur_usd_balance = self.accounts[acct].usd + new_usd_balance = cur_usd_balance * self.interest_rate_accum[epoch] / self.interest_rate_accum[account_last_epoch] + self.accounts[acct].usd = new_usd_balance + self.accounts[acct].last_epoch = epoch + self.usd_exposure += new_usd_balance - cur_usd_balance + + ethbal = self.accounts[acct].eth + + if new_usd_balance * usdval * 10 + ethbal * 9 < 0: + self.accounts[acct].eth = 0 + self.accounts[acct].usd = 0 + self.accounts[msg.sender].eth += ethbal / 50 + self.eth_exposure += -ethbal + ethbal / 50 + self.usd_exposure += new_usd_balance + return(1) + return(0) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellinghelper.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellinghelper.se new file mode 100644 index 000000000..0e522d6e8 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/schellinghelper.se @@ -0,0 +1 @@ +return(sha3([msg.sender, msg.data[0]], 2)) diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/short_namecoin.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/short_namecoin.se new file mode 100644 index 000000000..db327a77d --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/short_namecoin.se @@ -0,0 +1,3 @@ +def register(k, v): + if !self.storage[k]: + self.storage[k] = v diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/subcurrency.se b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/subcurrency.se new file mode 100644 index 000000000..fbda822b6 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/examples/subcurrency.se @@ -0,0 +1,11 @@ +def init(): + self.storage[msg.sender] = 1000000 + +def balance_query(k): + return(self.storage[addr]) + +def send(to, value): + fromvalue = self.storage[msg.sender] + if fromvalue >= value: + self.storage[from] = fromvalue - value + self.storage[to] += value diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/funcs.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/funcs.cpp new file mode 100644 index 000000000..ea9be14a6 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/funcs.cpp @@ -0,0 +1,35 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include "funcs.h" +#include "bignum.h" +#include "util.h" +#include "parser.h" +#include "lllparser.h" +#include "compiler.h" +#include "rewriter.h" +#include "tokenize.h" + +Node compileToLLL(std::string input) { + return rewrite(parseSerpent(input)); +} + +Node compileChunkToLLL(std::string input) { + return rewriteChunk(parseSerpent(input)); +} + +std::string compile(std::string input) { + return compileLLL(compileToLLL(input)); +} + +std::vector<Node> prettyCompile(std::string input) { + return prettyCompileLLL(compileToLLL(input)); +} + +std::string compileChunk(std::string input) { + return compileLLL(compileChunkToLLL(input)); +} + +std::vector<Node> prettyCompileChunk(std::string input) { + return prettyCompileLLL(compileChunkToLLL(input)); +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/funcs.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/funcs.h new file mode 100644 index 000000000..d9bf44549 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/funcs.h @@ -0,0 +1,35 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include "bignum.h" +#include "util.h" +#include "parser.h" +#include "lllparser.h" +#include "compiler.h" +#include "rewriter.h" +#include "tokenize.h" + +// Function listing: +// +// parseSerpent (serpent -> AST) std::string -> Node +// parseLLL (LLL -> AST) std::string -> Node +// rewrite (apply rewrite rules) Node -> Node +// compileToLLL (serpent -> LLL) std::string -> Node +// compileLLL (LLL -> EVMhex) Node -> std::string +// prettyCompileLLL (LLL -> EVMasm) Node -> std::vector<Node> +// prettyCompile (serpent -> EVMasm) std::string -> std::vector>Node> +// compile (serpent -> EVMhex) std::string -> std::string +// get_file_contents (filename -> file) std::string -> std::string +// exists (does file exist?) std::string -> bool + +Node compileToLLL(std::string input); + +Node compileChunkToLLL(std::string input); + +std::string compile(std::string input); + +std::vector<Node> prettyCompile(std::string input); + +std::string compileChunk(std::string input); + +std::vector<Node> prettyCompileChunk(std::string input); diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/functions.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/functions.cpp new file mode 100644 index 000000000..78e12e84a --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/functions.cpp @@ -0,0 +1,203 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "lllparser.h" +#include "bignum.h" +#include "optimize.h" +#include "rewriteutils.h" +#include "preprocess.h" +#include "functions.h" + +std::string getSignature(std::vector<Node> args) { + std::string o; + for (unsigned i = 0; i < args.size(); i++) { + if (args[i].val == ":" && args[i].args[1].val == "s") + o += "s"; + else if (args[i].val == ":" && args[i].args[1].val == "a") + o += "a"; + else + o += "i"; + } + return o; +} + +// Convert a list of arguments into a node containing a +// < datastart, datasz > pair + +Node packArguments(std::vector<Node> args, std::string sig, + int funId, Metadata m) { + // Plain old 32 byte arguments + std::vector<Node> nargs; + // Variable-sized arguments + std::vector<Node> vargs; + // Variable sizes + std::vector<Node> sizes; + // Is a variable an array? + std::vector<bool> isArray; + // Fill up above three argument lists + int argCount = 0; + for (unsigned i = 0; i < args.size(); i++) { + Metadata m = args[i].metadata; + if (args[i].val == "=") { + // do nothing + } + else { + // Determine the correct argument type + char argType; + if (sig.size() > 0) { + if (argCount >= (signed)sig.size()) + err("Too many args", m); + argType = sig[argCount]; + } + else argType = 'i'; + // Integer (also usable for short strings) + if (argType == 'i') { + if (args[i].val == ":") + err("Function asks for int, provided string or array", m); + nargs.push_back(args[i]); + } + // Long string + else if (argType == 's') { + if (args[i].val != ":") + err("Must specify string length", m); + vargs.push_back(args[i].args[0]); + sizes.push_back(args[i].args[1]); + isArray.push_back(false); + } + // Array + else if (argType == 'a') { + if (args[i].val != ":") + err("Must specify array length", m); + vargs.push_back(args[i].args[0]); + sizes.push_back(args[i].args[1]); + isArray.push_back(true); + } + else err("Invalid arg type in signature", m); + argCount++; + } + } + int static_arg_size = 1 + (vargs.size() + nargs.size()) * 32; + // Start off by saving the size variables and calculating the total + msn kwargs; + kwargs["funid"] = tkn(utd(funId), m); + std::string pattern = + "(with _sztot "+utd(static_arg_size)+" " + " (with _sizes (alloc "+utd(sizes.size() * 32)+") " + " (seq "; + for (unsigned i = 0; i < sizes.size(); i++) { + std::string sizeIncrement = + isArray[i] ? "(mul 32 _x)" : "_x"; + pattern += + "(with _x $sz"+utd(i)+"(seq " + " (mstore (add _sizes "+utd(i * 32)+") _x) " + " (set _sztot (add _sztot "+sizeIncrement+" )))) "; + kwargs["sz"+utd(i)] = sizes[i]; + } + // Allocate memory, and set first data byte + pattern += + "(with _datastart (alloc (add _sztot 32)) (seq " + " (mstore8 _datastart $funid) "; + // Copy over size variables + for (unsigned i = 0; i < sizes.size(); i++) { + int v = 1 + i * 32; + pattern += + " (mstore " + " (add _datastart "+utd(v)+") " + " (mload (add _sizes "+utd(v-1)+"))) "; + } + // Store normal arguments + for (unsigned i = 0; i < nargs.size(); i++) { + int v = 1 + (i + sizes.size()) * 32; + pattern += + " (mstore (add _datastart "+utd(v)+") $"+utd(i)+") "; + kwargs[utd(i)] = nargs[i]; + } + // Loop through variable-sized arguments, store them + pattern += + " (with _pos (add _datastart "+utd(static_arg_size)+") (seq"; + for (unsigned i = 0; i < vargs.size(); i++) { + std::string copySize = + isArray[i] ? "(mul 32 (mload (add _sizes "+utd(i * 32)+")))" + : "(mload (add _sizes "+utd(i * 32)+"))"; + pattern += + " (unsafe_mcopy _pos $vl"+utd(i)+" "+copySize+") " + " (set _pos (add _pos "+copySize+")) "; + kwargs["vl"+utd(i)] = vargs[i]; + } + // Return a 2-item array containing the start and size + pattern += " (array_lit _datastart _sztot))))))))"; + std::string prefix = "_temp_"+mkUniqueToken(); + // Fill in pattern, return triple + return subst(parseLLL(pattern), kwargs, prefix, m); +} + +// Create a node for argument unpacking +Node unpackArguments(std::vector<Node> vars, Metadata m) { + std::vector<std::string> varNames; + std::vector<std::string> longVarNames; + std::vector<bool> longVarIsArray; + // Fill in variable and long variable names, as well as which + // long variables are arrays and which are strings + for (unsigned i = 0; i < vars.size(); i++) { + if (vars[i].val == ":") { + if (vars[i].args.size() != 2) + err("Malformed def!", m); + longVarNames.push_back(vars[i].args[0].val); + std::string tag = vars[i].args[1].val; + if (tag == "s") + longVarIsArray.push_back(false); + else if (tag == "a") + longVarIsArray.push_back(true); + else + err("Function value can only be string or array", m); + } + else { + varNames.push_back(vars[i].val); + } + } + std::vector<Node> sub; + if (!varNames.size() && !longVarNames.size()) { + // do nothing if we have no arguments + } + else { + std::vector<Node> varNodes; + for (unsigned i = 0; i < longVarNames.size(); i++) + varNodes.push_back(token(longVarNames[i], m)); + for (unsigned i = 0; i < varNames.size(); i++) + varNodes.push_back(token(varNames[i], m)); + // Copy over variable lengths and short variables + for (unsigned i = 0; i < varNodes.size(); i++) { + int pos = 1 + i * 32; + std::string prefix = (i < longVarNames.size()) ? "_len_" : ""; + sub.push_back(asn("untyped", asn("set", + token(prefix+varNodes[i].val, m), + asn("calldataload", tkn(utd(pos), m), m), + m))); + } + // Copy over long variables + if (longVarNames.size() > 0) { + std::vector<Node> sub2; + int pos = varNodes.size() * 32 + 1; + Node tot = tkn("_tot", m); + for (unsigned i = 0; i < longVarNames.size(); i++) { + Node var = tkn(longVarNames[i], m); + Node varlen = longVarIsArray[i] + ? asn("mul", tkn("32", m), tkn("_len_"+longVarNames[i], m)) + : tkn("_len_"+longVarNames[i], m); + sub2.push_back(asn("untyped", + asn("set", var, asn("alloc", varlen)))); + sub2.push_back(asn("calldatacopy", var, tot, varlen)); + sub2.push_back(asn("set", tot, asn("add", tot, varlen))); + } + std::string prefix = "_temp_"+mkUniqueToken(); + sub.push_back(subst( + astnode("with", tot, tkn(utd(pos), m), asn("seq", sub2)), + msn(), + prefix, + m)); + } + } + return asn("seq", sub, m); +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/functions.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/functions.h new file mode 100644 index 000000000..68a1c69ce --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/functions.h @@ -0,0 +1,39 @@ +#ifndef ETHSERP_FUNCTIONS +#define ETHSERP_FUNCTIONS + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "lllparser.h" +#include "bignum.h" +#include "optimize.h" +#include "rewriteutils.h" +#include "preprocess.h" + + +class argPack { + public: + argPack(Node a, Node b, Node c) { + pre = a; + datastart = b; + datasz = c; + } + Node pre; + Node datastart; + Node datasz; +}; + +// Get a signature from a function +std::string getSignature(std::vector<Node> args); + +// Convert a list of arguments into a <pre, mstart, msize> node +// triple, given the signature of a function +Node packArguments(std::vector<Node> args, std::string sig, + int funId, Metadata m); + +// Create a node for argument unpacking +Node unpackArguments(std::vector<Node> vars, Metadata m); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/lllparser.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/lllparser.cpp new file mode 100644 index 000000000..ad4fbd52d --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/lllparser.cpp @@ -0,0 +1,70 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "lllparser.h" +#include "tokenize.h" + +struct _parseOutput { + Node node; + int newpos; +}; + +// Helper, returns subtree and position of start of next node +_parseOutput _parse(std::vector<Node> inp, int pos) { + Metadata met = inp[pos].metadata; + _parseOutput o; + // Bracket: keep grabbing tokens until we get to the + // corresponding closing bracket + if (inp[pos].val == "(" || inp[pos].val == "[") { + std::string fun, rbrack; + std::vector<Node> args; + pos += 1; + if (inp[pos].val == "[") { + fun = "access"; + rbrack = "]"; + } + else rbrack = ")"; + // First argument is the function + while (inp[pos].val != ")") { + _parseOutput po = _parse(inp, pos); + if (fun.length() == 0 && po.node.type == 1) { + std::cerr << "Error: first arg must be function\n"; + fun = po.node.val; + } + else if (fun.length() == 0) { + fun = po.node.val; + } + else { + args.push_back(po.node); + } + pos = po.newpos; + } + o.newpos = pos + 1; + o.node = astnode(fun, args, met); + } + // Normal token, return it and advance to next token + else { + o.newpos = pos + 1; + o.node = token(inp[pos].val, met); + } + return o; +} + +// stream of tokens -> lisp parse tree +Node parseLLLTokenStream(std::vector<Node> inp) { + _parseOutput o = _parse(inp, 0); + return o.node; +} + +// Parses LLL +Node parseLLL(std::string s, bool allowFileRead) { + std::string input = s; + std::string file = "main"; + if (exists(s) && allowFileRead) { + file = s; + input = get_file_contents(s); + } + return parseLLLTokenStream(tokenize(s, Metadata(file, 0, 0), true)); +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/lllparser.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/lllparser.h new file mode 100644 index 000000000..4bfa7b82e --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/lllparser.h @@ -0,0 +1,13 @@ +#ifndef ETHSERP_LLLPARSER +#define ETHSERP_LLLPARSER + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// LLL text -> parse tree +Node parseLLL(std::string s, bool allowFileRead=false); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/opcodes.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/opcodes.cpp new file mode 100644 index 000000000..b24144e46 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/opcodes.cpp @@ -0,0 +1,154 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "opcodes.h" +#include "util.h" +#include "bignum.h" + +Mapping mapping[] = { + Mapping("STOP", 0x00, 0, 0), + Mapping("ADD", 0x01, 2, 1), + Mapping("MUL", 0x02, 2, 1), + Mapping("SUB", 0x03, 2, 1), + Mapping("DIV", 0x04, 2, 1), + Mapping("SDIV", 0x05, 2, 1), + Mapping("MOD", 0x06, 2, 1), + Mapping("SMOD", 0x07, 2, 1), + Mapping("ADDMOD", 0x08, 3, 1), + Mapping("MULMOD", 0x09, 3, 1), + Mapping("EXP", 0x0a, 2, 1), + Mapping("SIGNEXTEND", 0x0b, 2, 1), + Mapping("LT", 0x10, 2, 1), + Mapping("GT", 0x11, 2, 1), + Mapping("SLT", 0x12, 2, 1), + Mapping("SGT", 0x13, 2, 1), + Mapping("EQ", 0x14, 2, 1), + Mapping("ISZERO", 0x15, 1, 1), + Mapping("AND", 0x16, 2, 1), + Mapping("OR", 0x17, 2, 1), + Mapping("XOR", 0x18, 2, 1), + Mapping("NOT", 0x19, 1, 1), + Mapping("BYTE", 0x1a, 2, 1), + Mapping("SHA3", 0x20, 2, 1), + Mapping("ADDRESS", 0x30, 0, 1), + Mapping("BALANCE", 0x31, 1, 1), + Mapping("ORIGIN", 0x32, 0, 1), + Mapping("CALLER", 0x33, 0, 1), + Mapping("CALLVALUE", 0x34, 0, 1), + Mapping("CALLDATALOAD", 0x35, 1, 1), + Mapping("CALLDATASIZE", 0x36, 0, 1), + Mapping("CALLDATACOPY", 0x37, 3, 0), + Mapping("CODESIZE", 0x38, 0, 1), + Mapping("CODECOPY", 0x39, 3, 0), + Mapping("GASPRICE", 0x3a, 0, 1), + Mapping("EXTCODESIZE", 0x3b, 1, 1), + Mapping("EXTCODECOPY", 0x3c, 4, 0), + Mapping("PREVHASH", 0x40, 0, 1), + Mapping("COINBASE", 0x41, 0, 1), + Mapping("TIMESTAMP", 0x42, 0, 1), + Mapping("NUMBER", 0x43, 0, 1), + Mapping("DIFFICULTY", 0x44, 0, 1), + Mapping("GASLIMIT", 0x45, 0, 1), + Mapping("POP", 0x50, 1, 0), + Mapping("MLOAD", 0x51, 1, 1), + Mapping("MSTORE", 0x52, 2, 0), + Mapping("MSTORE8", 0x53, 2, 0), + Mapping("SLOAD", 0x54, 1, 1), + Mapping("SSTORE", 0x55, 2, 0), + Mapping("JUMP", 0x56, 1, 0), + Mapping("JUMPI", 0x57, 2, 0), + Mapping("PC", 0x58, 0, 1), + Mapping("MSIZE", 0x59, 0, 1), + Mapping("GAS", 0x5a, 0, 1), + Mapping("JUMPDEST", 0x5b, 0, 0), + Mapping("LOG0", 0xa0, 2, 0), + Mapping("LOG1", 0xa1, 3, 0), + Mapping("LOG2", 0xa2, 4, 0), + Mapping("LOG3", 0xa3, 5, 0), + Mapping("LOG4", 0xa4, 6, 0), + Mapping("CREATE", 0xf0, 3, 1), + Mapping("CALL", 0xf1, 7, 1), + Mapping("CALLCODE", 0xf2, 7, 1), + Mapping("RETURN", 0xf3, 2, 0), + Mapping("SUICIDE", 0xff, 1, 0), + Mapping("---END---", 0x00, 0, 0), +}; + +std::map<std::string, std::vector<int> > opcodes; +std::map<int, std::string> reverseOpcodes; + +// Fetches everything EXCEPT PUSH1..32 +std::pair<std::string, std::vector<int> > _opdata(std::string ops, int opi) { + if (!opcodes.size()) { + int i = 0; + while (mapping[i].op != "---END---") { + Mapping mi = mapping[i]; + opcodes[mi.op] = triple(mi.opcode, mi.in, mi.out); + i++; + } + for (i = 1; i <= 16; i++) { + opcodes["DUP"+unsignedToDecimal(i)] = triple(0x7f + i, i, i+1); + opcodes["SWAP"+unsignedToDecimal(i)] = triple(0x8f + i, i+1, i+1); + } + for (std::map<std::string, std::vector<int> >::iterator it=opcodes.begin(); + it != opcodes.end(); + it++) { + reverseOpcodes[(*it).second[0]] = (*it).first; + } + } + ops = upperCase(ops); + std::string op; + std::vector<int> opdata; + op = reverseOpcodes.count(opi) ? reverseOpcodes[opi] : ""; + opdata = opcodes.count(ops) ? opcodes[ops] : triple(-1, -1, -1); + return std::pair<std::string, std::vector<int> >(op, opdata); +} + +int opcode(std::string op) { + return _opdata(op, -1).second[0]; +} + +int opinputs(std::string op) { + return _opdata(op, -1).second[1]; +} + +int opoutputs(std::string op) { + return _opdata(op, -1).second[2]; +} + +std::string op(int opcode) { + return _opdata("", opcode).first; +} + +std::string lllSpecials[][3] = { + { "ref", "1", "1" }, + { "get", "1", "1" }, + { "set", "2", "2" }, + { "with", "3", "3" }, + { "comment", "0", "2147483647" }, + { "ops", "0", "2147483647" }, + { "lll", "2", "2" }, + { "seq", "0", "2147483647" }, + { "if", "3", "3" }, + { "unless", "2", "2" }, + { "until", "2", "2" }, + { "alloc", "1", "1" }, + { "---END---", "0", "0" }, +}; + +std::map<std::string, std::pair<int, int> > lllMap; + +// Is a function name one of the valid functions above? +bool isValidLLLFunc(std::string f, int argc) { + if (lllMap.size() == 0) { + for (int i = 0; ; i++) { + if (lllSpecials[i][0] == "---END---") break; + lllMap[lllSpecials[i][0]] = std::pair<int, int>( + dtu(lllSpecials[i][1]), dtu(lllSpecials[i][2])); + } + } + return lllMap.count(f) + && argc >= lllMap[f].first + && argc <= lllMap[f].second; +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/opcodes.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/opcodes.h new file mode 100644 index 000000000..41423c169 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/opcodes.h @@ -0,0 +1,45 @@ +#ifndef ETHSERP_OPCODES +#define ETHSERP_OPCODES + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +class Mapping { + public: + Mapping(std::string Op, int Opcode, int In, int Out) { + op = Op; + opcode = Opcode; + in = In; + out = Out; + } + std::string op; + int opcode; + int in; + int out; +}; + +extern Mapping mapping[]; + +extern std::map<std::string, std::vector<int> > opcodes; +extern std::map<int, std::string> reverseOpcodes; + +std::pair<std::string, std::vector<int> > _opdata(std::string ops, int opi); + +int opcode(std::string op); + +int opinputs(std::string op); + +int opoutputs(std::string op); + +std::string op(int opcode); + +extern std::string lllSpecials[][3]; + +extern std::map<std::string, std::pair<int, int> > lllMap; + +bool isValidLLLFunc(std::string f, int argc); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/optimize.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/optimize.cpp new file mode 100644 index 000000000..e689fcb69 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/optimize.cpp @@ -0,0 +1,98 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "lllparser.h" +#include "bignum.h" + +// Compile-time arithmetic calculations +Node optimize(Node inp) { + if (inp.type == TOKEN) { + Node o = tryNumberize(inp); + if (decimalGt(o.val, tt256, true)) + err("Value too large (exceeds 32 bytes or 2^256)", inp.metadata); + return o; + } + for (unsigned i = 0; i < inp.args.size(); i++) { + inp.args[i] = optimize(inp.args[i]); + } + // Arithmetic-specific transform + if (inp.val == "+") inp.val = "add"; + if (inp.val == "*") inp.val = "mul"; + if (inp.val == "-") inp.val = "sub"; + if (inp.val == "/") inp.val = "sdiv"; + if (inp.val == "^") inp.val = "exp"; + if (inp.val == "**") inp.val = "exp"; + if (inp.val == "%") inp.val = "smod"; + // Degenerate cases for add and mul + if (inp.args.size() == 2) { + if (inp.val == "add" && inp.args[0].type == TOKEN && + inp.args[0].val == "0") { + Node x = inp.args[1]; + inp = x; + } + if (inp.val == "add" && inp.args[1].type == TOKEN && + inp.args[1].val == "0") { + Node x = inp.args[0]; + inp = x; + } + if (inp.val == "mul" && inp.args[0].type == TOKEN && + inp.args[0].val == "1") { + Node x = inp.args[1]; + inp = x; + } + if (inp.val == "mul" && inp.args[1].type == TOKEN && + inp.args[1].val == "1") { + Node x = inp.args[0]; + inp = x; + } + } + // Arithmetic computation + if (inp.args.size() == 2 + && inp.args[0].type == TOKEN + && inp.args[1].type == TOKEN) { + std::string o; + if (inp.val == "add") { + o = decimalMod(decimalAdd(inp.args[0].val, inp.args[1].val), tt256); + } + else if (inp.val == "sub") { + if (decimalGt(inp.args[0].val, inp.args[1].val, true)) + o = decimalSub(inp.args[0].val, inp.args[1].val); + } + else if (inp.val == "mul") { + o = decimalMod(decimalMul(inp.args[0].val, inp.args[1].val), tt256); + } + else if (inp.val == "div" && inp.args[1].val != "0") { + o = decimalDiv(inp.args[0].val, inp.args[1].val); + } + else if (inp.val == "sdiv" && inp.args[1].val != "0" + && decimalGt(tt255, inp.args[0].val) + && decimalGt(tt255, inp.args[1].val)) { + o = decimalDiv(inp.args[0].val, inp.args[1].val); + } + else if (inp.val == "mod" && inp.args[1].val != "0") { + o = decimalMod(inp.args[0].val, inp.args[1].val); + } + else if (inp.val == "smod" && inp.args[1].val != "0" + && decimalGt(tt255, inp.args[0].val) + && decimalGt(tt255, inp.args[1].val)) { + o = decimalMod(inp.args[0].val, inp.args[1].val); + } + else if (inp.val == "exp") { + o = decimalModExp(inp.args[0].val, inp.args[1].val, tt256); + } + if (o.length()) return token(o, inp.metadata); + } + return inp; +} + +// Is a node degenerate (ie. trivial to calculate) ? +bool isDegenerate(Node n) { + return optimize(n).type == TOKEN; +} + +// Is a node purely arithmetic? +bool isPureArithmetic(Node n) { + return isNumberLike(optimize(n)); +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/optimize.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/optimize.h new file mode 100644 index 000000000..06ea3bba1 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/optimize.h @@ -0,0 +1,19 @@ +#ifndef ETHSERP_OPTIMIZER +#define ETHSERP_OPTIMIZER + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// Compile-time arithmetic calculations +Node optimize(Node inp); + +// Is a node degenerate (ie. trivial to calculate) ? +bool isDegenerate(Node n); + +// Is a node purely arithmetic? +bool isPureArithmetic(Node n); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/parser.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/parser.cpp new file mode 100644 index 000000000..5e8c459c3 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/parser.cpp @@ -0,0 +1,430 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "parser.h" +#include "tokenize.h" + +// Extended BEDMAS precedence order +int precedence(Node tok) { + std::string v = tok.val; + if (v == ".") return -1; + else if (v == "!" || v == "not") return 1; + else if (v=="^" || v == "**") return 2; + else if (v=="*" || v=="/" || v=="%") return 3; + else if (v=="+" || v=="-") return 4; + else if (v=="<" || v==">" || v=="<=" || v==">=") return 5; + else if (v=="&" || v=="|" || v=="xor" || v=="==" || v == "!=") return 6; + else if (v=="&&" || v=="and") return 7; + else if (v=="||" || v=="or") return 8; + else if (v=="=") return 10; + else if (v=="+=" || v=="-=" || v=="*=" || v=="/=" || v=="%=") return 10; + else if (v==":" || v == "::") return 11; + else return 0; +} + +// Token classification for shunting-yard purposes +int toktype(Node tok) { + if (tok.type == ASTNODE) return COMPOUND; + std::string v = tok.val; + if (v == "(" || v == "[" || v == "{") return LPAREN; + else if (v == ")" || v == "]" || v == "}") return RPAREN; + else if (v == ",") return COMMA; + else if (v == "!" || v == "~" || v == "not") return UNARY_OP; + else if (precedence(tok) > 0) return BINARY_OP; + else if (precedence(tok) < 0) return TOKEN_SPLITTER; + if (tok.val[0] != '"' && tok.val[0] != '\'') { + for (unsigned i = 0; i < tok.val.length(); i++) { + if (chartype(tok.val[i]) == SYMB) { + err("Invalid symbol: "+tok.val, tok.metadata); + } + } + } + return ALPHANUM; +} + + +// Converts to reverse polish notation +std::vector<Node> shuntingYard(std::vector<Node> tokens) { + std::vector<Node> iq; + for (int i = tokens.size() - 1; i >= 0; i--) { + iq.push_back(tokens[i]); + } + std::vector<Node> oq; + std::vector<Node> stack; + Node prev, tok; + int prevtyp = 0, toktyp = 0; + + while (iq.size()) { + prev = tok; + prevtyp = toktyp; + tok = iq.back(); + toktyp = toktype(tok); + iq.pop_back(); + // Alphanumerics go straight to output queue + if (toktyp == ALPHANUM) { + oq.push_back(tok); + } + // Left parens go on stack and output queue + else if (toktyp == LPAREN) { + while (stack.size() && toktype(stack.back()) == TOKEN_SPLITTER) { + oq.push_back(stack.back()); + stack.pop_back(); + } + if (prevtyp != ALPHANUM && prevtyp != RPAREN) { + oq.push_back(token("id", tok.metadata)); + } + stack.push_back(tok); + oq.push_back(tok); + } + // If rparen, keep moving from stack to output queue until lparen + else if (toktyp == RPAREN) { + while (stack.size() && toktype(stack.back()) != LPAREN) { + oq.push_back(stack.back()); + stack.pop_back(); + } + if (stack.size()) { + stack.pop_back(); + } + oq.push_back(tok); + } + else if (toktyp == UNARY_OP) { + stack.push_back(tok); + } + // If token splitter, just push it to the stack + else if (toktyp == TOKEN_SPLITTER) { + while (stack.size() && toktype(stack.back()) == TOKEN_SPLITTER) { + oq.push_back(stack.back()); + stack.pop_back(); + } + stack.push_back(tok); + } + // If binary op, keep popping from stack while higher bedmas precedence + else if (toktyp == BINARY_OP) { + if (tok.val == "-" && prevtyp != ALPHANUM && prevtyp != RPAREN) { + stack.push_back(tok); + oq.push_back(token("0", tok.metadata)); + } + else { + int prec = precedence(tok); + while (stack.size() + && (toktype(stack.back()) == BINARY_OP + || toktype(stack.back()) == UNARY_OP + || toktype(stack.back()) == TOKEN_SPLITTER) + && precedence(stack.back()) <= prec) { + oq.push_back(stack.back()); + stack.pop_back(); + } + stack.push_back(tok); + } + } + // Comma means finish evaluating the argument + else if (toktyp == COMMA) { + while (stack.size() && toktype(stack.back()) != LPAREN) { + oq.push_back(stack.back()); + stack.pop_back(); + } + } + } + while (stack.size()) { + oq.push_back(stack.back()); + stack.pop_back(); + } + return oq; +} + +// Converts reverse polish notation into tree +Node treefy(std::vector<Node> stream) { + std::vector<Node> iq; + for (int i = stream.size() -1; i >= 0; i--) { + iq.push_back(stream[i]); + } + std::vector<Node> oq; + while (iq.size()) { + Node tok = iq.back(); + iq.pop_back(); + int typ = toktype(tok); + // If unary, take node off end of oq and wrap it with the operator + // If binary, do the same with two nodes + if (typ == UNARY_OP || typ == BINARY_OP || typ == TOKEN_SPLITTER) { + std::vector<Node> args; + int rounds = (typ == UNARY_OP) ? 1 : 2; + for (int i = 0; i < rounds; i++) { + if (oq.size() == 0) { + err("Line malformed, not enough args for "+tok.val, + tok.metadata); + } + args.push_back(oq.back()); + oq.pop_back(); + } + std::vector<Node> args2; + while (args.size()) { + args2.push_back(args.back()); + args.pop_back(); + } + oq.push_back(astnode(tok.val, args2, tok.metadata)); + } + // If rparen, keep grabbing until we get to an lparen + else if (typ == RPAREN) { + std::vector<Node> args; + while (1) { + if (toktype(oq.back()) == LPAREN) break; + args.push_back(oq.back()); + oq.pop_back(); + if (!oq.size()) err("Bracket without matching", tok.metadata); + } + oq.pop_back(); + args.push_back(oq.back()); + oq.pop_back(); + // We represent a[b] as (access a b) + if (tok.val == "]") + args.push_back(token("access", tok.metadata)); + if (args.back().type == ASTNODE) + args.push_back(token("fun", tok.metadata)); + std::string fun = args.back().val; + args.pop_back(); + // We represent [1,2,3] as (array_lit 1 2 3) + if (fun == "access" && args.size() && args.back().val == "id") { + fun = "array_lit"; + args.pop_back(); + } + std::vector<Node> args2; + while (args.size()) { + args2.push_back(args.back()); + args.pop_back(); + } + // When evaluating 2 + (3 * 5), the shunting yard algo turns that + // into 2 ( id 3 5 * ) +, effectively putting "id" as a dummy + // function where the algo was expecting a function to call the + // thing inside the brackets. This reverses that step + if (fun == "id" && args2.size() == 1) { + oq.push_back(args2[0]); + } + else { + oq.push_back(astnode(fun, args2, tok.metadata)); + } + } + else oq.push_back(tok); + // This is messy, but has to be done. Import/inset other files here + std::string v = oq.back().val; + if ((v == "inset" || v == "import" || v == "create") + && oq.back().args.size() == 1 + && oq.back().args[0].type == TOKEN) { + int lastSlashPos = tok.metadata.file.rfind("/"); + std::string root; + if (lastSlashPos >= 0) + root = tok.metadata.file.substr(0, lastSlashPos) + "/"; + else + root = ""; + std::string filename = oq.back().args[0].val; + filename = filename.substr(1, filename.length() - 2); + if (!exists(root + filename)) + err("File does not exist: "+root + filename, tok.metadata); + oq.back().args.pop_back(); + oq.back().args.push_back(parseSerpent(root + filename)); + } + //Useful for debugging + //for (int i = 0; i < oq.size(); i++) { + // std::cerr << printSimple(oq[i]) << " "; + //} + //std::cerr << " <-\n"; + } + // Output must have one argument + if (oq.size() == 0) { + err("Output blank", Metadata()); + } + else if (oq.size() > 1) { + return asn("multi", oq, oq[0].metadata); + } + + return oq[0]; +} + + +// Parses one line of serpent +Node parseSerpentTokenStream(std::vector<Node> s) { + return treefy(shuntingYard(s)); +} + + +// Count spaces at beginning of line +int spaceCount(std::string s) { + unsigned pos = 0; + while (pos < s.length() && (s[pos] == ' ' || s[pos] == '\t')) + pos++; + return pos; +} + +// Is this a command that takes an argument on the same line? +bool bodied(std::string tok) { + return tok == "if" || tok == "elif" || tok == "while" + || tok == "with" || tok == "def" || tok == "extern" + || tok == "data" || tok == "assert" || tok == "return" + || tok == "fun" || tok == "scope" || tok == "macro" + || tok == "type"; +} + +// Are the two commands meant to continue each other? +bool bodiedContinued(std::string prev, std::string tok) { + return (prev == "if" && tok == "elif") + || (prev == "elif" && tok == "else") + || (prev == "elif" && tok == "elif") + || (prev == "if" && tok == "else"); +} + +// Is a line of code empty? +bool isLineEmpty(std::string line) { + std::vector<Node> tokens = tokenize(line); + if (!tokens.size() || tokens[0].val == "#" || tokens[0].val == "//") + return true; + return false; +} + +// Parse lines of serpent (helper function) +Node parseLines(std::vector<std::string> lines, Metadata metadata, int sp) { + std::vector<Node> o; + int origLine = metadata.ln; + unsigned i = 0; + while (i < lines.size()) { + metadata.ln = origLine + i; + std::string main = lines[i]; + if (isLineEmpty(main)) { + i += 1; + continue; + } + int spaces = spaceCount(main); + if (spaces != sp) { + err("Indent mismatch", metadata); + } + // Tokenize current line + std::vector<Node> tokens = tokenize(main.substr(sp), metadata); + // Remove comments + std::vector<Node> tokens2; + for (unsigned j = 0; j < tokens.size(); j++) { + if (tokens[j].val == "#" || tokens[j].val == "//") break; + tokens2.push_back(tokens[j]); + } + bool expectingChildBlock = false; + if (tokens2.size() > 0 && tokens2.back().val == ":") { + tokens2.pop_back(); + expectingChildBlock = true; + } + // Parse current line + Node out = parseSerpentTokenStream(tokens2); + // Parse child block + int childIndent = 999999; + std::vector<std::string> childBlock; + while (1) { + i++; + if (i >= lines.size()) + break; + bool ile = isLineEmpty(lines[i]); + if (!ile) { + int spaces = spaceCount(lines[i]); + if (spaces <= sp) break; + childBlock.push_back(lines[i]); + if (spaces < childIndent) childIndent = spaces; + } + else childBlock.push_back(""); + } + // Child block empty? + bool cbe = true; + for (unsigned i = 0; i < childBlock.size(); i++) { + if (childBlock[i].length() > 0) { cbe = false; break; } + } + // Add child block to AST + if (expectingChildBlock) { + if (cbe) + err("Expected indented child block!", out.metadata); + out.type = ASTNODE; + metadata.ln += 1; + out.args.push_back(parseLines(childBlock, metadata, childIndent)); + metadata.ln -= 1; + } + else if (!cbe) + err("Did not expect indented child block!", out.metadata); + else if (out.args.size() && out.args[out.args.size() - 1].val == ":") { + Node n = out.args[out.args.size() - 1]; + out.args.pop_back(); + out.args.push_back(n.args[0]); + out.args.push_back(n.args[1]); + } + // Bring back if / elif into AST + if (bodied(tokens[0].val)) { + if (out.val != "multi") { + // token not being used in bodied form + } + else if (out.args[0].val == "id") + out = astnode(tokens[0].val, out.args[1].args, out.metadata); + else if (out.args[0].type == TOKEN) { + std::vector<Node> out2; + for (unsigned i = 1; i < out.args.size(); i++) + out2.push_back(out.args[i]); + out = astnode(tokens[0].val, out2, out.metadata); + } + else + out = astnode("fun", out.args, out.metadata); + } + // Multi not supported + if (out.val == "multi") + err("Multiple expressions or unclosed bracket", out.metadata); + // Convert top-level colon expressions into non-colon expressions; + // makes if statements and the like equivalent indented or not + //if (out.val == ":" && out.args[0].type == TOKEN) + // out = asn(out.args[0].val, out.args[1], out.metadata); + //if (bodied(tokens[0].val) && out.args[0].val == ":") + // out = asn(tokens[0].val, out.args[0].args); + if (o.size() == 0 || o.back().type == TOKEN) { + o.push_back(out); + continue; + } + // This is a little complicated. Basically, the idea here is to build + // constructions like [if [< x 5] [a] [elif [< x 10] [b] [else [c]]]] + std::vector<Node> u; + u.push_back(o.back()); + if (bodiedContinued(o.back().val, out.val)) { + while (1) { + if (!bodiedContinued(u.back().val, out.val)) { + u.pop_back(); + break; + } + if (!u.back().args.size() + || !bodiedContinued(u.back().val, u.back().args.back().val)) { + break; + } + u.push_back(u.back().args.back()); + } + u.back().args.push_back(out); + while (u.size() > 1) { + Node v = u.back(); + u.pop_back(); + u.back().args.pop_back(); + u.back().args.push_back(v); + } + o.pop_back(); + o.push_back(u[0]); + } + else o.push_back(out); + } + if (o.size() == 1) + return o[0]; + else if (o.size()) + return astnode("seq", o, o[0].metadata); + else + return astnode("seq", o, Metadata()); +} + +// Parses serpent code +Node parseSerpent(std::string s) { + std::string input = s; + std::string file = "main"; + if (exists(s)) { + file = s; + input = get_file_contents(s); + } + return parseLines(splitLines(input), Metadata(file, 0, 0), 0); +} + + +using namespace std; diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/parser.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/parser.h new file mode 100644 index 000000000..e3632220a --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/parser.h @@ -0,0 +1,13 @@ +#ifndef ETHSERP_PARSER +#define ETHSERP_PARSER + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// Serpent text -> parse tree +Node parseSerpent(std::string s); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/preprocess.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/preprocess.cpp new file mode 100644 index 000000000..3f08ea8b1 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/preprocess.cpp @@ -0,0 +1,299 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "lllparser.h" +#include "bignum.h" +#include "rewriteutils.h" +#include "optimize.h" +#include "preprocess.h" +#include "functions.h" +#include "opcodes.h" + +// Convert a function of the form (def (f x y z) (do stuff)) into +// (if (first byte of ABI is correct) (seq (setup x y z) (do stuff))) +Node convFunction(Node node, int functionCount) { + std::string prefix = "_temp"+mkUniqueToken()+"_"; + Metadata m = node.metadata; + + if (node.args.size() != 2) + err("Malformed def!", m); + // Collect the list of variable names and variable byte counts + Node unpack = unpackArguments(node.args[0].args, m); + // And the actual code + Node body = node.args[1]; + // Main LLL-based function body + return astnode("if", + astnode("eq", + astnode("get", token("__funid", m), m), + token(unsignedToDecimal(functionCount), m), + m), + astnode("seq", unpack, body, m)); +} + +// Populate an svObj with the arguments needed to determine +// the storage position of a node +svObj getStorageVars(svObj pre, Node node, std::string prefix, + int index) { + Metadata m = node.metadata; + if (!pre.globalOffset.size()) pre.globalOffset = "0"; + std::vector<Node> h; + std::vector<std::string> coefficients; + // Array accesses or atoms + if (node.val == "access" || node.type == TOKEN) { + std::string tot = "1"; + h = listfyStorageAccess(node); + coefficients.push_back("1"); + for (unsigned i = h.size() - 1; i >= 1; i--) { + // Array sizes must be constant or at least arithmetically + // evaluable at compile time + if (!isPureArithmetic(h[i])) + err("Array size must be fixed value", m); + // Create a list of the coefficient associated with each + // array index + coefficients.push_back(decimalMul(coefficients.back(), h[i].val)); + } + } + // Tuples + else { + int startc; + // Handle the (fun <fun_astnode> args...) case + if (node.val == "fun") { + startc = 1; + h = listfyStorageAccess(node.args[0]); + } + // Handle the (<fun_name> args...) case, which + // the serpent parser produces when the function + // is a simple name and not a complex astnode + else { + startc = 0; + h = listfyStorageAccess(token(node.val, m)); + } + svObj sub = pre; + sub.globalOffset = "0"; + // Evaluate tuple elements recursively + for (unsigned i = startc; i < node.args.size(); i++) { + sub = getStorageVars(sub, + node.args[i], + prefix+h[0].val.substr(2)+".", + i-startc); + } + coefficients.push_back(sub.globalOffset); + for (unsigned i = h.size() - 1; i >= 1; i--) { + // Array sizes must be constant or at least arithmetically + // evaluable at compile time + if (!isPureArithmetic(h[i])) + err("Array size must be fixed value", m); + // Create a list of the coefficient associated with each + // array index + coefficients.push_back(decimalMul(coefficients.back(), h[i].val)); + } + pre.offsets = sub.offsets; + pre.coefficients = sub.coefficients; + pre.nonfinal = sub.nonfinal; + pre.nonfinal[prefix+h[0].val.substr(2)] = true; + } + pre.coefficients[prefix+h[0].val.substr(2)] = coefficients; + pre.offsets[prefix+h[0].val.substr(2)] = pre.globalOffset; + pre.indices[prefix+h[0].val.substr(2)] = index; + if (decimalGt(tt176, coefficients.back())) + pre.globalOffset = decimalAdd(pre.globalOffset, coefficients.back()); + return pre; +} + +// Preprocess input containing functions +// +// localExterns is a map of the form, eg, +// +// { x: { foo: 0, bar: 1, baz: 2 }, y: { qux: 0, foo: 1 } ... } +// +// localExternSigs is a map of the form, eg, +// +// { x : { foo: iii, bar: iis, baz: ia }, y: { qux: i, foo: as } ... } +// +// Signifying that x.foo = 0, x.baz = 2, y.foo = 1, etc +// and that x.foo has three integers as arguments, x.bar has two +// integers and a variable-length string, and baz has an integer +// and an array +// +// globalExterns is a one-level map, eg from above +// +// { foo: 1, bar: 1, baz: 2, qux: 0 } +// +// globalExternSigs is a one-level map, eg from above +// +// { foo: as, bar: iis, baz: ia, qux: i} +// +// Note that globalExterns and globalExternSigs may be ambiguous +// Also, a null signature implies an infinite tail of integers +preprocessResult preprocessInit(Node inp) { + Metadata m = inp.metadata; + if (inp.val != "seq") + inp = astnode("seq", inp, m); + std::vector<Node> empty = std::vector<Node>(); + Node init = astnode("seq", empty, m); + Node shared = astnode("seq", empty, m); + std::vector<Node> any; + std::vector<Node> functions; + preprocessAux out = preprocessAux(); + out.localExterns["self"] = std::map<std::string, int>(); + int functionCount = 0; + int storageDataCount = 0; + for (unsigned i = 0; i < inp.args.size(); i++) { + Node obj = inp.args[i]; + // Functions + if (obj.val == "def") { + if (obj.args.size() == 0) + err("Empty def", m); + std::string funName = obj.args[0].val; + // Init, shared and any are special functions + if (funName == "init" || funName == "shared" || funName == "any") { + if (obj.args[0].args.size()) + err(funName+" cannot have arguments", m); + } + if (funName == "init") init = obj.args[1]; + else if (funName == "shared") shared = obj.args[1]; + else if (funName == "any") any.push_back(obj.args[1]); + else { + // Other functions + functions.push_back(convFunction(obj, functionCount)); + out.localExterns["self"][obj.args[0].val] = functionCount; + out.localExternSigs["self"][obj.args[0].val] + = getSignature(obj.args[0].args); + functionCount++; + } + } + // Extern declarations + else if (obj.val == "extern") { + std::string externName = obj.args[0].val; + Node al = obj.args[1]; + if (!out.localExterns.count(externName)) + out.localExterns[externName] = std::map<std::string, int>(); + for (unsigned i = 0; i < al.args.size(); i++) { + if (al.args[i].val == ":") { + std::string v = al.args[i].args[0].val; + std::string sig = al.args[i].args[1].val; + out.globalExterns[v] = i; + out.globalExternSigs[v] = sig; + out.localExterns[externName][v] = i; + out.localExternSigs[externName][v] = sig; + } + else { + std::string v = al.args[i].val; + out.globalExterns[v] = i; + out.globalExternSigs[v] = ""; + out.localExterns[externName][v] = i; + out.localExternSigs[externName][v] = ""; + } + } + } + // Custom macros + else if (obj.val == "macro") { + // Rules for valid macros: + // + // There are only four categories of valid macros: + // + // 1. a macro where the outer function is something + // which is NOT an existing valid function/extern/datum + // 2. a macro of the form set(c(x), d) where c must NOT + // be an existing valid function/extern/datum + // 3. something of the form access(c(x)), where c must NOT + // be an existing valid function/extern/datum + // 4. something of the form set(access(c(x)), d) where c must + // NOT be an existing valid function/extern/datum + bool valid = false; + Node pattern = obj.args[0]; + Node substitution = obj.args[1]; + if (opcode(pattern.val) < 0 && !isValidFunctionName(pattern.val)) + valid = true; + if (pattern.val == "set" && + opcode(pattern.args[0].val) < 0 && + !isValidFunctionName(pattern.args[0].val)) + valid = true; + if (pattern.val == "access" && + opcode(pattern.args[0].val) < 0 && + !isValidFunctionName(pattern.args[0].val)) + if (pattern.val == "set" && + pattern.args[0].val == "access" && + opcode(pattern.args[0].args[0].val) < 0 && + !isValidFunctionName(pattern.args[0].args[0].val)) + valid = true; + if (valid) { + out.customMacros.push_back(rewriteRule(pattern, substitution)); + } + } + // Variable types + else if (obj.val == "type") { + std::string typeName = obj.args[0].val; + std::vector<Node> vars = obj.args[1].args; + for (unsigned i = 0; i < vars.size(); i++) + out.types[vars[i].val] = typeName; + } + // Storage variables/structures + else if (obj.val == "data") { + out.storageVars = getStorageVars(out.storageVars, + obj.args[0], + "", + storageDataCount); + storageDataCount += 1; + } + else any.push_back(obj); + } + std::vector<Node> main; + if (shared.args.size()) main.push_back(shared); + if (init.args.size()) main.push_back(init); + + std::vector<Node> code; + if (shared.args.size()) code.push_back(shared); + for (unsigned i = 0; i < any.size(); i++) + code.push_back(any[i]); + for (unsigned i = 0; i < functions.size(); i++) + code.push_back(functions[i]); + Node codeNode; + if (functions.size() > 0) { + codeNode = astnode("with", + token("__funid", m), + astnode("byte", + token("0", m), + astnode("calldataload", token("0", m), m), + m), + astnode("seq", code, m), + m); + } + else codeNode = astnode("seq", code, m); + main.push_back(astnode("~return", + token("0", m), + astnode("lll", + codeNode, + token("0", m), + m), + m)); + + + Node result; + if (main.size() == 1) result = main[0]; + else result = astnode("seq", main, inp.metadata); + return preprocessResult(result, out); +} + +preprocessResult processTypes (preprocessResult pr) { + preprocessAux aux = pr.second; + Node node = pr.first; + if (node.type == TOKEN && aux.types.count(node.val)) { + node = asn(aux.types[node.val], node, node.metadata); + } + else if (node.val == "untyped") + return preprocessResult(node.args[0], aux); + else { + for (unsigned i = 0; i < node.args.size(); i++) { + node.args[i] = + processTypes(preprocessResult(node.args[i], aux)).first; + } + } + return preprocessResult(node, aux); +} + +preprocessResult preprocess(Node n) { + return processTypes(preprocessInit(n)); +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/preprocess.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/preprocess.h new file mode 100644 index 000000000..944436aef --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/preprocess.h @@ -0,0 +1,58 @@ +#ifndef ETHSERP_PREPROCESSOR +#define ETHSERP_PREPROCESSOR + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// Storage variable index storing object +struct svObj { + std::map<std::string, std::string> offsets; + std::map<std::string, int> indices; + std::map<std::string, std::vector<std::string> > coefficients; + std::map<std::string, bool> nonfinal; + std::string globalOffset; +}; + +class rewriteRule { + public: + rewriteRule(Node p, Node s) { + pattern = p; + substitution = s; + } + Node pattern; + Node substitution; +}; + + +// Preprocessing result storing object +class preprocessAux { + public: + preprocessAux() { + globalExterns = std::map<std::string, int>(); + localExterns = std::map<std::string, std::map<std::string, int> >(); + localExterns["self"] = std::map<std::string, int>(); + } + std::map<std::string, int> globalExterns; + std::map<std::string, std::string> globalExternSigs; + std::map<std::string, std::map<std::string, int> > localExterns; + std::map<std::string, std::map<std::string, std::string> > localExternSigs; + std::vector<rewriteRule> customMacros; + std::map<std::string, std::string> types; + svObj storageVars; +}; + +#define preprocessResult std::pair<Node, preprocessAux> + +// Populate an svObj with the arguments needed to determine +// the storage position of a node +svObj getStorageVars(svObj pre, Node node, std::string prefix="", + int index=0); + +// Preprocess a function (see cpp for details) +preprocessResult preprocess(Node inp); + + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/pyserpent.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/pyserpent.cpp new file mode 100644 index 000000000..38398aa46 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/pyserpent.cpp @@ -0,0 +1,173 @@ +#include <Python.h> +#include "structmember.h" + +#include <stdlib.h> +#include <stdio.h> +#include <iostream> +#include "funcs.h" + +#define PYMETHOD(name, FROM, method, TO) \ + static PyObject * name(PyObject *, PyObject *args) { \ + try { \ + FROM(med) \ + return TO(method(med)); \ + } \ + catch (std::string e) { \ + PyErr_SetString(PyExc_Exception, e.c_str()); \ + return NULL; \ + } \ + } + +#define FROMSTR(v) \ + const char *command; \ + int len; \ + if (!PyArg_ParseTuple(args, "s#", &command, &len)) \ + return NULL; \ + std::string v = std::string(command, len); \ + +#define FROMNODE(v) \ + PyObject *node; \ + if (!PyArg_ParseTuple(args, "O", &node)) \ + return NULL; \ + Node v = cppifyNode(node); + +#define FROMLIST(v) \ + PyObject *node; \ + if (!PyArg_ParseTuple(args, "O", &node)) \ + return NULL; \ + std::vector<Node> v = cppifyNodeList(node); + +// Convert metadata into python wrapper form [file, ln, ch] +PyObject* pyifyMetadata(Metadata m) { + PyObject* a = PyList_New(0); + PyList_Append(a, Py_BuildValue("s#", m.file.c_str(), m.file.length())); + PyList_Append(a, Py_BuildValue("i", m.ln)); + PyList_Append(a, Py_BuildValue("i", m.ch)); + return a; +} + +// Convert node into python wrapper form +// [token=0/astnode=1, val, metadata, args] +PyObject* pyifyNode(Node n) { + PyObject* a = PyList_New(0); + PyList_Append(a, Py_BuildValue("i", n.type == ASTNODE)); + PyList_Append(a, Py_BuildValue("s#", n.val.c_str(), n.val.length())); + PyList_Append(a, pyifyMetadata(n.metadata)); + for (unsigned i = 0; i < n.args.size(); i++) + PyList_Append(a, pyifyNode(n.args[i])); + return a; +} + +// Convert string into python wrapper form +PyObject* pyifyString(std::string s) { + return Py_BuildValue("s#", s.c_str(), s.length()); +} + +// Convert list of nodes into python wrapper form +PyObject* pyifyNodeList(std::vector<Node> n) { + PyObject* a = PyList_New(0); + for (unsigned i = 0; i < n.size(); i++) + PyList_Append(a, pyifyNode(n[i])); + return a; +} + +// Convert pyobject int into normal form +int cppifyInt(PyObject* o) { + int out; + if (!PyArg_Parse(o, "i", &out)) + err("Argument should be integer", Metadata()); + return out; +} + +// Convert pyobject string into normal form +std::string cppifyString(PyObject* o) { + const char *command; + if (!PyArg_Parse(o, "s", &command)) + err("Argument should be string", Metadata()); + return std::string(command); +} + +// Convert metadata from python wrapper form +Metadata cppifyMetadata(PyObject* o) { + std::string file = cppifyString(PyList_GetItem(o, 0)); + int ln = cppifyInt(PyList_GetItem(o, 1)); + int ch = cppifyInt(PyList_GetItem(o, 2)); + return Metadata(file, ln, ch); +} + +// Convert node from python wrapper form +Node cppifyNode(PyObject* o) { + Node n; + int isAstNode = cppifyInt(PyList_GetItem(o, 0)); + n.type = isAstNode ? ASTNODE : TOKEN; + n.val = cppifyString(PyList_GetItem(o, 1)); + n.metadata = cppifyMetadata(PyList_GetItem(o, 2)); + std::vector<Node> args; + for (int i = 3; i < PyList_Size(o); i++) { + args.push_back(cppifyNode(PyList_GetItem(o, i))); + } + n.args = args; + return n; +} + +//Convert list of nodes into normal form +std::vector<Node> cppifyNodeList(PyObject* o) { + std::vector<Node> out; + for (int i = 0; i < PyList_Size(o); i++) { + out.push_back(cppifyNode(PyList_GetItem(o,i))); + } + return out; +} + +PYMETHOD(ps_compile, FROMSTR, compile, pyifyString) +PYMETHOD(ps_compile_chunk, FROMSTR, compileChunk, pyifyString) +PYMETHOD(ps_compile_to_lll, FROMSTR, compileToLLL, pyifyNode) +PYMETHOD(ps_compile_chunk_to_lll, FROMSTR, compileChunkToLLL, pyifyNode) +PYMETHOD(ps_compile_lll, FROMNODE, compileLLL, pyifyString) +PYMETHOD(ps_parse, FROMSTR, parseSerpent, pyifyNode) +PYMETHOD(ps_rewrite, FROMNODE, rewrite, pyifyNode) +PYMETHOD(ps_rewrite_chunk, FROMNODE, rewriteChunk, pyifyNode) +PYMETHOD(ps_pretty_compile, FROMSTR, prettyCompile, pyifyNodeList) +PYMETHOD(ps_pretty_compile_chunk, FROMSTR, prettyCompileChunk, pyifyNodeList) +PYMETHOD(ps_pretty_compile_lll, FROMNODE, prettyCompileLLL, pyifyNodeList) +PYMETHOD(ps_serialize, FROMLIST, serialize, pyifyString) +PYMETHOD(ps_deserialize, FROMSTR, deserialize, pyifyNodeList) +PYMETHOD(ps_parse_lll, FROMSTR, parseLLL, pyifyNode) + + +static PyMethodDef PyextMethods[] = { + {"compile", ps_compile, METH_VARARGS, + "Compile code."}, + {"compile_chunk", ps_compile_chunk, METH_VARARGS, + "Compile code chunk (no wrappers)."}, + {"compile_to_lll", ps_compile_to_lll, METH_VARARGS, + "Compile code to LLL."}, + {"compile_chunk_to_lll", ps_compile_chunk_to_lll, METH_VARARGS, + "Compile code chunk to LLL (no wrappers)."}, + {"compile_lll", ps_compile_lll, METH_VARARGS, + "Compile LLL to EVM."}, + {"parse", ps_parse, METH_VARARGS, + "Parse serpent"}, + {"rewrite", ps_rewrite, METH_VARARGS, + "Rewrite parsed serpent to LLL"}, + {"rewrite_chunk", ps_rewrite_chunk, METH_VARARGS, + "Rewrite parsed serpent to LLL (no wrappers)"}, + {"pretty_compile", ps_pretty_compile, METH_VARARGS, + "Compile to EVM opcodes"}, + {"pretty_compile_chunk", ps_pretty_compile_chunk, METH_VARARGS, + "Compile chunk to EVM opcodes (no wrappers)"}, + {"pretty_compile_lll", ps_pretty_compile_lll, METH_VARARGS, + "Compile LLL to EVM opcodes"}, + {"serialize", ps_serialize, METH_VARARGS, + "Convert EVM opcodes to bin"}, + {"deserialize", ps_deserialize, METH_VARARGS, + "Convert EVM bin to opcodes"}, + {"parse_lll", ps_parse_lll, METH_VARARGS, + "Parse LLL"}, + {NULL, NULL, 0, NULL} /* Sentinel */ +}; + +PyMODINIT_FUNC initserpent_pyext(void) +{ + Py_InitModule( "serpent_pyext", PyextMethods ); +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/pyserpent.py b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/pyserpent.py new file mode 100644 index 000000000..2103b48fe --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/pyserpent.py @@ -0,0 +1 @@ +from serpent import * diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriter.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriter.cpp new file mode 100644 index 000000000..4cdce4f0a --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriter.cpp @@ -0,0 +1,804 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "lllparser.h" +#include "bignum.h" +#include "optimize.h" +#include "rewriteutils.h" +#include "preprocess.h" +#include "functions.h" +#include "opcodes.h" + +// Rewrite rules +std::string macros[][2] = { + { + "(seq $x)", + "$x" + }, + { + "(seq (seq) $x)", + "$x" + }, + { + "(+= $a $b)", + "(set $a (+ $a $b))" + }, + { + "(*= $a $b)", + "(set $a (* $a $b))" + }, + { + "(-= $a $b)", + "(set $a (- $a $b))" + }, + { + "(/= $a $b)", + "(set $a (/ $a $b))" + }, + { + "(%= $a $b)", + "(set $a (% $a $b))" + }, + { + "(^= $a $b)", + "(set $a (^ $a $b))" + }, + { + "(!= $a $b)", + "(iszero (eq $a $b))" + }, + { + "(assert $x)", + "(unless $x (stop))" + }, + { + "(min $a $b)", + "(with $1 $a (with $2 $b (if (lt $1 $2) $1 $2)))" + }, + { + "(max $a $b)", + "(with $1 $a (with $2 $b (if (lt $1 $2) $2 $1)))" + }, + { + "(smin $a $b)", + "(with $1 $a (with $2 $b (if (slt $1 $2) $1 $2)))" + }, + { + "(smax $a $b)", + "(with $1 $a (with $2 $b (if (slt $1 $2) $2 $1)))" + }, + { + "(if $cond $do (else $else))", + "(if $cond $do $else)" + }, + { + "(code $code)", + "$code" + }, + { + "(slice $arr $pos)", + "(add $arr (mul 32 $pos))", + }, + { + "(array $len)", + "(alloc (mul 32 $len))" + }, + { + "(while $cond $do)", + "(until (iszero $cond) $do)", + }, + { + "(while (iszero $cond) $do)", + "(until $cond $do)", + }, + { + "(if $cond $do)", + "(unless (iszero $cond) $do)", + }, + { + "(if (iszero $cond) $do)", + "(unless $cond $do)", + }, + { + "(access (. self storage) $ind)", + "(sload $ind)" + }, + { + "(access $var $ind)", + "(mload (add $var (mul 32 $ind)))" + }, + { + "(set (access (. self storage) $ind) $val)", + "(sstore $ind $val)" + }, + { + "(set (access $var $ind) $val)", + "(mstore (add $var (mul 32 $ind)) $val)" + }, + { + "(getch $var $ind)", + "(mod (mload (sub (add $var $ind) 31)) 256)" + }, + { + "(setch $var $ind $val)", + "(mstore8 (add $var $ind) $val)", + }, + { + "(send $to $value)", + "(~call (sub (gas) 25) $to $value 0 0 0 0)" + }, + { + "(send $gas $to $value)", + "(~call $gas $to $value 0 0 0 0)" + }, + { + "(sha3 $x)", + "(seq (set $1 $x) (~sha3 (ref $1) 32))" + }, + { + "(sha3 $mstart (= chars $msize))", + "(~sha3 $mstart $msize)" + }, + { + "(sha3 $mstart $msize)", + "(~sha3 $mstart (mul 32 $msize))" + }, + { + "(id $0)", + "$0" + }, + { + "(return $x)", + "(seq (set $1 $x) (~return (ref $1) 32))" + }, + { + "(return $mstart (= chars $msize))", + "(~return $mstart $msize)" + }, + { + "(return $start $len)", + "(~return $start (mul 32 $len))" + }, + { + "(&& $x $y)", + "(if $x $y 0)" + }, + { + "(|| $x $y)", + "(with $1 $x (if $1 $1 $y))" + }, + { + "(>= $x $y)", + "(iszero (slt $x $y))" + }, + { + "(<= $x $y)", + "(iszero (sgt $x $y))" + }, + { + "(create $code)", + "(create 0 $code)" + }, + { + "(create $endowment $code)", + "(with $1 (msize) (create $endowment (get $1) (lll (outer $code) (msize))))" + }, + { + "(sha256 $x)", + "(with $1 (alloc 64) (seq (mstore (add (get $1) 32) $x) (pop (~call 101 2 0 (add (get $1) 32) 32 (get $1) 32)) (mload (get $1))))" + }, + { + "(sha256 $arr (= chars $sz))", + "(with $1 (alloc 32) (seq (pop (~call 101 2 0 $arr $sz (get $1) 32)) (mload (get $1))))" + }, + { + "(sha256 $arr $sz)", + "(with $1 (alloc 32) (seq (pop (~call 101 2 0 $arr (mul 32 $sz) (get $1) 32)) (mload (get $1))))" + }, + { + "(ripemd160 $x)", + "(with $1 (alloc 64) (seq (mstore (add (get $1) 32) $x) (pop (~call 101 3 0 (add (get $1) 32) 32 (get $1) 32)) (mload (get $1))))" + }, + { + "(ripemd160 $arr (= chars $sz))", + "(with $1 (alloc 32) (seq (pop (~call 101 3 0 $arr $sz (mload $1) 32)) (mload (get $1))))" + }, + { + "(ripemd160 $arr $sz)", + "(with $1 (alloc 32) (seq (pop (~call 101 3 0 $arr (mul 32 $sz) (get $1) 32)) (mload (get $1))))" + }, + { + "(ecrecover $h $v $r $s)", + "(with $1 (alloc 160) (seq (mstore (get $1) $h) (mstore (add (get $1) 32) $v) (mstore (add (get $1) 64) $r) (mstore (add (get $1) 96) $s) (pop (~call 101 1 0 (get $1) 128 (add (get $1 128)) 32)) (mload (add (get $1) 128))))" + }, + { + "(inset $x)", + "$x" + }, + { + "(create $x)", + "(with $1 (msize) (create $val (get $1) (lll $code (get $1))))" + }, + { + "(with (= $var $val) $cond)", + "(with $var $val $cond)" + }, + { + "(log $t1)", + "(~log1 0 0 $t1)" + }, + { + "(log $t1 $t2)", + "(~log2 0 0 $t1 $t2)" + }, + { + "(log $t1 $t2 $t3)", + "(~log3 0 0 $t1 $t2 $t3)" + }, + { + "(log $t1 $t2 $t3 $t4)", + "(~log4 0 0 $t1 $t2 $t3 $t4)" + }, + { + "(logarr $a $sz)", + "(~log0 $a (mul 32 $sz))" + }, + { + "(logarr $a $sz $t1)", + "(~log1 $a (mul 32 $sz) $t1)" + }, + { + "(logarr $a $sz $t1 $t2)", + "(~log2 $a (mul 32 $sz) $t1 $t2)" + }, + { + "(logarr $a $sz $t1 $t2 $t3)", + "(~log3 $a (mul 32 $sz) $t1 $t2 $t3)" + }, + { + "(logarr $a $sz $t1 $t2 $t3 $t4)", + "(~log4 $a (mul 32 $sz) $t1 $t2 $t3 $t4)" + }, + { + "(save $loc $array (= chars $count))", + "(with $location (ref $loc) (with $c $count (with $end (div $c 32) (with $i 0 (seq (while (slt $i $end) (seq (sstore (add $i $location) (access $array $i)) (set $i (add $i 1)))) (sstore (add $i $location) (~and (access $array $i) (sub 0 (exp 256 (sub 32 (mod $c 32)))))))))))" + }, + { + "(save $loc $array $count)", + "(with $location (ref $loc) (with $end $count (with $i 0 (while (slt $i $end) (seq (sstore (add $i $location) (access $array $i)) (set $i (add $i 1)))))))" + }, + { + "(load $loc (= chars $count))", + "(with $location (ref $loc) (with $c $count (with $a (alloc $c) (with $i 0 (seq (while (slt $i (div $c 32)) (seq (set (access $a $i) (sload (add $location $i))) (set $i (add $i 1)))) (set (access $a $i) (~and (sload (add $location $i)) (sub 0 (exp 256 (sub 32 (mod $c 32)))))) $a)))))" + }, + { + "(load $loc $count)", + "(with $location (ref $loc) (with $c $count (with $a (alloc $c) (with $i 0 (seq (while (slt $i $c) (seq (set (access $a $i) (sload (add $location $i))) (set $i (add $i 1)))) $a)))))" + }, + { + "(unsafe_mcopy $to $from $sz)", + "(with _sz $sz (with _from $from (with _to $to (seq (comment STARTING UNSAFE MCOPY) (with _i 0 (while (lt _i _sz) (seq (mstore (add $to _i) (mload (add _from _i))) (set _i (add _i 32)))))))))" + }, + { + "(mcopy $to $from $_sz)", + "(with _to $to (with _from $from (with _sz $sz (seq (comment STARTING MCOPY (with _i 0 (seq (while (lt (add _i 31) _sz) (seq (mstore (add _to _i) (mload (add _from _i))) (set _i (add _i 32)))) (with _mask (exp 256 (sub 32 (mod _sz 32))) (mstore (add $to _i) (add (mod (mload (add $to _i)) _mask) (and (mload (add $from _i)) (sub 0 _mask))))))))))))" + }, + { "(. msg sender)", "(caller)" }, + { "(. msg value)", "(callvalue)" }, + { "(. tx gasprice)", "(gasprice)" }, + { "(. tx origin)", "(origin)" }, + { "(. tx gas)", "(gas)" }, + { "(. $x balance)", "(balance $x)" }, + { "self", "(address)" }, + { "(. block prevhash)", "(prevhash)" }, + { "(. block coinbase)", "(coinbase)" }, + { "(. block timestamp)", "(timestamp)" }, + { "(. block number)", "(number)" }, + { "(. block difficulty)", "(difficulty)" }, + { "(. block gaslimit)", "(gaslimit)" }, + { "stop", "(stop)" }, + { "---END---", "" } //Keep this line at the end of the list +}; + +std::vector<rewriteRule> nodeMacros; + +// Token synonyms +std::string synonyms[][2] = { + { "or", "||" }, + { "and", "&&" }, + { "|", "~or" }, + { "&", "~and" }, + { "elif", "if" }, + { "!", "iszero" }, + { "~", "~not" }, + { "not", "iszero" }, + { "string", "alloc" }, + { "+", "add" }, + { "-", "sub" }, + { "*", "mul" }, + { "/", "sdiv" }, + { "^", "exp" }, + { "**", "exp" }, + { "%", "smod" }, + { "<", "slt" }, + { ">", "sgt" }, + { "=", "set" }, + { "==", "eq" }, + { ":", "kv" }, + { "---END---", "" } //Keep this line at the end of the list +}; + +// Custom setters (need to be registered separately +// for use with managed storage) +std::string setters[][2] = { + { "+=", "+" }, + { "-=", "-" }, + { "*=", "*" }, + { "/=", "/" }, + { "%=", "%" }, + { "^=", "^" }, + { "---END---", "" } //Keep this line at the end of the list +}; + +// Processes mutable array literals +Node array_lit_transform(Node node) { + std::string prefix = "_temp"+mkUniqueToken() + "_"; + Metadata m = node.metadata; + std::map<std::string, Node> d; + std::string o = "(seq (set $arr (alloc "+utd(node.args.size()*32)+"))"; + for (unsigned i = 0; i < node.args.size(); i++) { + o += " (mstore (add (get $arr) "+utd(i * 32)+") $"+utd(i)+")"; + d[utd(i)] = node.args[i]; + } + o += " (get $arr))"; + return subst(parseLLL(o), d, prefix, m); +} + + +Node apply_rules(preprocessResult pr); + +// Transform "<variable>.<fun>(args...)" into +// a call +Node dotTransform(Node node, preprocessAux aux) { + Metadata m = node.metadata; + // We're gonna make lots of temporary variables, + // so set up a unique flag for them + std::string prefix = "_temp"+mkUniqueToken()+"_"; + // Check that the function name is a token + if (node.args[0].args[1].type == ASTNODE) + err("Function name must be static", m); + + Node dotOwner = node.args[0].args[0]; + std::string dotMember = node.args[0].args[1].val; + // kwargs = map of special arguments + std::map<std::string, Node> kwargs; + kwargs["value"] = token("0", m); + kwargs["gas"] = subst(parseLLL("(- (gas) 25)"), msn(), prefix, m); + // Search for as=? and call=code keywords, and isolate the actual + // function arguments + std::vector<Node> fnargs; + std::string as = ""; + std::string op = "call"; + for (unsigned i = 1; i < node.args.size(); i++) { + fnargs.push_back(node.args[i]); + Node arg = fnargs.back(); + if (arg.val == "=" || arg.val == "set") { + if (arg.args[0].val == "as") + as = arg.args[1].val; + if (arg.args[0].val == "call" && arg.args[1].val == "code") + op = "callcode"; + if (arg.args[0].val == "gas") + kwargs["gas"] = arg.args[1]; + if (arg.args[0].val == "value") + kwargs["value"] = arg.args[1]; + if (arg.args[0].val == "outsz") + kwargs["outsz"] = arg.args[1]; + } + } + if (dotOwner.val == "self") { + if (as.size()) err("Cannot use \"as\" when calling self!", m); + as = dotOwner.val; + } + // Determine the funId and sig assuming the "as" keyword was used + int funId = 0; + std::string sig; + if (as.size() > 0 && aux.localExterns.count(as)) { + if (!aux.localExterns[as].count(dotMember)) + err("Invalid call: "+printSimple(dotOwner)+"."+dotMember, m); + funId = aux.localExterns[as][dotMember]; + sig = aux.localExternSigs[as][dotMember]; + } + // Determine the funId and sig otherwise + else if (!as.size()) { + if (!aux.globalExterns.count(dotMember)) + err("Invalid call: "+printSimple(dotOwner)+"."+dotMember, m); + std::string key = unsignedToDecimal(aux.globalExterns[dotMember]); + funId = aux.globalExterns[dotMember]; + sig = aux.globalExternSigs[dotMember]; + } + else err("Invalid call: "+printSimple(dotOwner)+"."+dotMember, m); + // Pack arguments + kwargs["data"] = packArguments(fnargs, sig, funId, m); + kwargs["to"] = dotOwner; + Node main; + // Pack output + if (!kwargs.count("outsz")) { + main = parseLLL( + "(with _data $data (seq " + "(pop (~"+op+" $gas $to $value (access _data 0) (access _data 1) (ref $dataout) 32))" + "(get $dataout)))"); + } + else { + main = parseLLL( + "(with _data $data (with _outsz (mul 32 $outsz) (with _out (alloc _outsz) (seq " + "(pop (~"+op+" $gas $to $value (access _data 0) (access _data 1) _out _outsz))" + "(get _out)))))"); + } + // Set up main call + + Node o = subst(main, kwargs, prefix, m); + return o; +} + +// Transform an access of the form self.bob, self.users[5], etc into +// a storage access +// +// There exist two types of objects: finite objects, and infinite +// objects. Finite objects are packed optimally tightly into storage +// accesses; for example: +// +// data obj[100](a, b[2][4], c) +// +// obj[0].a -> 0 +// obj[0].b[0][0] -> 1 +// obj[0].b[1][3] -> 8 +// obj[45].c -> 459 +// +// Infinite objects are accessed by sha3([v1, v2, v3 ... ]), where +// the values are a list of array indices and keyword indices, for +// example: +// data obj[](a, b[2][4], c) +// data obj2[](a, b[][], c) +// +// obj[0].a -> sha3([0, 0, 0]) +// obj[5].b[1][3] -> sha3([0, 5, 1, 1, 3]) +// obj[45].c -> sha3([0, 45, 2]) +// obj2[0].a -> sha3([1, 0, 0]) +// obj2[5].b[1][3] -> sha3([1, 5, 1, 1, 3]) +// obj2[45].c -> sha3([1, 45, 2]) +Node storageTransform(Node node, preprocessAux aux, + bool mapstyle=false, bool ref=false) { + Metadata m = node.metadata; + // Get a list of all of the "access parameters" used in order + // eg. self.users[5].cow[4][m[2]][woof] -> + // [--self, --users, 5, --cow, 4, m[2], woof] + std::vector<Node> hlist = listfyStorageAccess(node); + // For infinite arrays, the terms array will just provide a list + // of indices. For finite arrays, it's a list of index*coefficient + std::vector<Node> terms; + std::string offset = "0"; + std::string prefix = ""; + std::string varPrefix = "_temp"+mkUniqueToken()+"_"; + int c = 0; + std::vector<std::string> coefficients; + coefficients.push_back(""); + for (unsigned i = 1; i < hlist.size(); i++) { + // We pre-add the -- flag to parameter-like terms. For example, + // self.users[m] -> [--self, --users, m] + // self.users.m -> [--self, --users, --m] + if (hlist[i].val.substr(0, 2) == "--") { + prefix += hlist[i].val.substr(2) + "."; + std::string tempPrefix = prefix.substr(0, prefix.size()-1); + if (!aux.storageVars.offsets.count(tempPrefix)) + return node; + if (c < (signed)coefficients.size() - 1) + err("Too few array index lookups", m); + if (c > (signed)coefficients.size() - 1) + err("Too many array index lookups", m); + coefficients = aux.storageVars.coefficients[tempPrefix]; + // If the size of an object exceeds 2^176, we make it an infinite + // array + if (decimalGt(coefficients.back(), tt176) && !mapstyle) + return storageTransform(node, aux, true, ref); + offset = decimalAdd(offset, aux.storageVars.offsets[tempPrefix]); + c = 0; + if (mapstyle) + terms.push_back(token(unsignedToDecimal( + aux.storageVars.indices[tempPrefix]))); + } + else if (mapstyle) { + terms.push_back(hlist[i]); + c += 1; + } + else { + if (c > (signed)coefficients.size() - 2) + err("Too many array index lookups", m); + terms.push_back( + astnode("mul", + hlist[i], + token(coefficients[coefficients.size() - 2 - c], m), + m)); + + c += 1; + } + } + if (aux.storageVars.nonfinal.count(prefix.substr(0, prefix.size()-1))) + err("Storage variable access not deep enough", m); + if (c < (signed)coefficients.size() - 1) { + err("Too few array index lookups", m); + } + if (c > (signed)coefficients.size() - 1) { + err("Too many array index lookups", m); + } + Node o; + if (mapstyle) { + std::string t = "_temp_"+mkUniqueToken(); + std::vector<Node> sub; + for (unsigned i = 0; i < terms.size(); i++) + sub.push_back(asn("mstore", + asn("add", + tkn(utd(i * 32), m), + asn("get", tkn(t+"pos", m), m), + m), + terms[i], + m)); + sub.push_back(tkn(t+"pos", m)); + Node main = asn("with", + tkn(t+"pos", m), + asn("alloc", tkn(utd(terms.size() * 32), m), m), + asn("seq", sub, m), + m); + Node sz = token(utd(terms.size() * 32), m); + o = astnode("~sha3", + main, + sz, + m); + } + else { + // We add up all the index*coefficients + Node out = token(offset, node.metadata); + for (unsigned i = 0; i < terms.size(); i++) { + std::vector<Node> temp; + temp.push_back(out); + temp.push_back(terms[i]); + out = astnode("add", temp, node.metadata); + } + o = out; + } + if (ref) return o; + else return astnode("sload", o, node.metadata); +} + + +// Recursively applies rewrite rules +std::pair<Node, bool> apply_rules_iter(preprocessResult pr) { + bool changed = false; + Node node = pr.first; + // If the rewrite rules have not yet been parsed, parse them + if (!nodeMacros.size()) { + for (int i = 0; i < 9999; i++) { + std::vector<Node> o; + if (macros[i][0] == "---END---") break; + nodeMacros.push_back(rewriteRule( + parseLLL(macros[i][0]), + parseLLL(macros[i][1]) + )); + } + } + // Assignment transformations + for (int i = 0; i < 9999; i++) { + if (setters[i][0] == "---END---") break; + if (node.val == setters[i][0]) { + node = astnode("=", + node.args[0], + astnode(setters[i][1], + node.args[0], + node.args[1], + node.metadata), + node.metadata); + } + } + // Do nothing to macros + if (node.val == "macro") { + return std::pair<Node, bool>(node, changed); + } + // Ignore comments + if (node.val == "comment") { + return std::pair<Node, bool>(node, changed); + } + // Special storage transformation + if (isNodeStorageVariable(node)) { + node = storageTransform(node, pr.second); + changed = true; + } + if (node.val == "ref" && isNodeStorageVariable(node.args[0])) { + node = storageTransform(node.args[0], pr.second, false, true); + changed = true; + } + if (node.val == "=" && isNodeStorageVariable(node.args[0])) { + Node t = storageTransform(node.args[0], pr.second); + if (t.val == "sload") { + std::vector<Node> o; + o.push_back(t.args[0]); + o.push_back(node.args[1]); + node = astnode("sstore", o, node.metadata); + } + changed = true; + } + // Main code + unsigned pos = 0; + std::string prefix = "_temp"+mkUniqueToken()+"_"; + while(1) { + if (synonyms[pos][0] == "---END---") { + break; + } + else if (node.type == ASTNODE && node.val == synonyms[pos][0]) { + node.val = synonyms[pos][1]; + changed = true; + } + pos++; + } + for (pos = 0; pos < nodeMacros.size() + pr.second.customMacros.size(); pos++) { + rewriteRule macro = pos < nodeMacros.size() + ? nodeMacros[pos] + : pr.second.customMacros[pos - nodeMacros.size()]; + matchResult mr = match(macro.pattern, node); + if (mr.success) { + node = subst(macro.substitution, mr.map, prefix, node.metadata); + std::pair<Node, bool> o = + apply_rules_iter(preprocessResult(node, pr.second)); + o.second = true; + return o; + } + } + // Special transformations + if (node.val == "outer") { + node = apply_rules(preprocess(node.args[0])); + changed = true; + } + if (node.val == "array_lit") { + node = array_lit_transform(node); + changed = true; + } + if (node.val == "fun" && node.args[0].val == ".") { + node = dotTransform(node, pr.second); + changed = true; + } + if (node.type == ASTNODE) { + unsigned i = 0; + if (node.val == "set" || node.val == "ref" + || node.val == "get" || node.val == "with") { + if (node.args[0].val.size() > 0 && node.args[0].val[0] != '\'' + && node.args[0].type == TOKEN && node.args[0].val[0] != '$') { + node.args[0].val = "'" + node.args[0].val; + changed = true; + } + i = 1; + } + else if (node.val == "arglen") { + node.val = "get"; + node.args[0].val = "'_len_" + node.args[0].val; + i = 1; + changed = true; + } + for (; i < node.args.size(); i++) { + std::pair<Node, bool> r = + apply_rules_iter(preprocessResult(node.args[i], pr.second)); + node.args[i] = r.first; + changed = changed || r.second; + } + } + else if (node.type == TOKEN && !isNumberLike(node)) { + if (node.val.size() >= 2 + && node.val[0] == '"' + && node.val[node.val.size() - 1] == '"') { + std::string bin = node.val.substr(1, node.val.size() - 2); + unsigned sz = bin.size(); + std::vector<Node> o; + for (unsigned i = 0; i < sz; i += 32) { + std::string t = binToNumeric(bin.substr(i, 32)); + if ((sz - i) < 32 && (sz - i) > 0) { + while ((sz - i) < 32) { + t = decimalMul(t, "256"); + i--; + } + i = sz; + } + o.push_back(token(t, node.metadata)); + } + node = astnode("array_lit", o, node.metadata); + std::pair<Node, bool> r = + apply_rules_iter(preprocessResult(node, pr.second)); + node = r.first; + changed = true; + } + else if (node.val.size() && node.val[0] != '\'' && node.val[0] != '$') { + node.val = "'" + node.val; + std::vector<Node> args; + args.push_back(node); + std::string v = node.val.substr(1); + node = astnode("get", args, node.metadata); + changed = true; + } + } + return std::pair<Node, bool>(node, changed); +} + +Node apply_rules(preprocessResult pr) { + for (unsigned i = 0; i < pr.second.customMacros.size(); i++) { + pr.second.customMacros[i].pattern = + apply_rules(preprocessResult(pr.second.customMacros[i].pattern, preprocessAux())); + } + while (1) { + //std::cerr << printAST(pr.first) << + // " " << pr.second.customMacros.size() << "\n"; + std::pair<Node, bool> r = apply_rules_iter(pr); + if (!r.second) { + return r.first; + } + pr.first = r.first; + } +} + +Node validate(Node inp) { + Metadata m = inp.metadata; + if (inp.type == ASTNODE) { + int i = 0; + while(validFunctions[i][0] != "---END---") { + if (inp.val == validFunctions[i][0]) { + std::string sz = unsignedToDecimal(inp.args.size()); + if (decimalGt(validFunctions[i][1], sz)) { + err("Too few arguments for "+inp.val, inp.metadata); + } + if (decimalGt(sz, validFunctions[i][2])) { + err("Too many arguments for "+inp.val, inp.metadata); + } + } + i++; + } + } + for (unsigned i = 0; i < inp.args.size(); i++) validate(inp.args[i]); + return inp; +} + +Node postValidate(Node inp) { + // This allows people to use ~x as a way of having functions with the same + // name and arity as macros; the idea is that ~x is a "final" form, and + // should not be remacroed, but it is converted back at the end + if (inp.val.size() > 0 && inp.val[0] == '~') { + inp.val = inp.val.substr(1); + } + if (inp.type == ASTNODE) { + if (inp.val == ".") + err("Invalid object member (ie. a foo.bar not mapped to anything)", + inp.metadata); + else if (opcode(inp.val) >= 0) { + if ((signed)inp.args.size() < opinputs(inp.val)) + err("Too few arguments for "+inp.val, inp.metadata); + if ((signed)inp.args.size() > opinputs(inp.val)) + err("Too many arguments for "+inp.val, inp.metadata); + } + else if (isValidLLLFunc(inp.val, inp.args.size())) { + // do nothing + } + else err ("Invalid argument count or LLL function: "+inp.val, inp.metadata); + for (unsigned i = 0; i < inp.args.size(); i++) { + inp.args[i] = postValidate(inp.args[i]); + } + } + return inp; +} + +Node rewrite(Node inp) { + return postValidate(optimize(apply_rules(preprocess(inp)))); +} + +Node rewriteChunk(Node inp) { + return postValidate(optimize(apply_rules( + preprocessResult( + validate(inp), preprocessAux())))); +} + +using namespace std; diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriter.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriter.h new file mode 100644 index 000000000..716815cee --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriter.h @@ -0,0 +1,16 @@ +#ifndef ETHSERP_REWRITER +#define ETHSERP_REWRITER + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// Applies rewrite rules +Node rewrite(Node inp); + +// Applies rewrite rules adding without wrapper +Node rewriteChunk(Node inp); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriteutils.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriteutils.cpp new file mode 100644 index 000000000..0d810bdbc --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriteutils.cpp @@ -0,0 +1,211 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "lllparser.h" +#include "bignum.h" +#include "rewriteutils.h" +#include "optimize.h" + +// Valid functions and their min and max argument counts +std::string validFunctions[][3] = { + { "if", "2", "3" }, + { "unless", "2", "2" }, + { "while", "2", "2" }, + { "until", "2", "2" }, + { "alloc", "1", "1" }, + { "array", "1", "1" }, + { "call", "2", tt256 }, + { "callcode", "2", tt256 }, + { "create", "1", "4" }, + { "getch", "2", "2" }, + { "setch", "3", "3" }, + { "sha3", "1", "2" }, + { "return", "1", "2" }, + { "inset", "1", "1" }, + { "min", "2", "2" }, + { "max", "2", "2" }, + { "array_lit", "0", tt256 }, + { "seq", "0", tt256 }, + { "log", "1", "6" }, + { "outer", "1", "1" }, + { "set", "2", "2" }, + { "get", "1", "1" }, + { "ref", "1", "1" }, + { "declare", "1", tt256 }, + { "with", "3", "3" }, + { "outer", "1", "1" }, + { "mcopy", "3", "3" }, + { "unsafe_mcopy", "3", "3" }, + { "save", "3", "3" }, + { "load", "2", "2" }, + { "---END---", "", "" } //Keep this line at the end of the list +}; + +std::map<std::string, bool> vfMap; + +// Is a function name one of the valid functions above? +bool isValidFunctionName(std::string f) { + if (vfMap.size() == 0) { + for (int i = 0; ; i++) { + if (validFunctions[i][0] == "---END---") break; + vfMap[validFunctions[i][0]] = true; + } + } + return vfMap.count(f); +} + +// Cool function for debug purposes (named cerrStringList to make +// all prints searchable via 'cerr') +void cerrStringList(std::vector<std::string> s, std::string suffix) { + for (unsigned i = 0; i < s.size(); i++) std::cerr << s[i] << " "; + std::cerr << suffix << "\n"; +} + +// Convert: +// self.cow -> ["cow"] +// self.horse[0] -> ["horse", "0"] +// self.a[6][7][self.storage[3]].chicken[9] -> +// ["6", "7", (sload 3), "chicken", "9"] +std::vector<Node> listfyStorageAccess(Node node) { + std::vector<Node> out; + std::vector<Node> nodez; + nodez.push_back(node); + while (1) { + if (nodez.back().type == TOKEN) { + out.push_back(token("--" + nodez.back().val, node.metadata)); + std::vector<Node> outrev; + for (int i = (signed)out.size() - 1; i >= 0; i--) { + outrev.push_back(out[i]); + } + return outrev; + } + if (nodez.back().val == ".") + nodez.back().args[1].val = "--" + nodez.back().args[1].val; + if (nodez.back().args.size() == 0) + err("Error parsing storage variable statement", node.metadata); + if (nodez.back().args.size() == 1) + out.push_back(token(tt256m1, node.metadata)); + else + out.push_back(nodez.back().args[1]); + nodez.push_back(nodez.back().args[0]); + } +} + +// Is the given node something of the form +// self.cow +// self.horse[0] +// self.a[6][7][self.storage[3]].chicken[9] +bool isNodeStorageVariable(Node node) { + std::vector<Node> nodez; + nodez.push_back(node); + while (1) { + if (nodez.back().type == TOKEN) return false; + if (nodez.back().args.size() == 0) return false; + if (nodez.back().val != "." && nodez.back().val != "access") + return false; + if (nodez.back().args[0].val == "self") return true; + nodez.push_back(nodez.back().args[0]); + } +} + +// Main pattern matching routine, for those patterns that can be expressed +// using our standard mini-language above +// +// Returns two values. First, a boolean to determine whether the node matches +// the pattern, second, if the node does match then a map mapping variables +// in the pattern to nodes +matchResult match(Node p, Node n) { + matchResult o; + o.success = false; + if (p.type == TOKEN) { + if (p.val == n.val && n.type == TOKEN) o.success = true; + else if (p.val[0] == '$' || p.val[0] == '@') { + o.success = true; + o.map[p.val.substr(1)] = n; + } + } + else if (n.type==TOKEN || p.val!=n.val || p.args.size()!=n.args.size()) { + // do nothing + } + else { + for (unsigned i = 0; i < p.args.size(); i++) { + matchResult oPrime = match(p.args[i], n.args[i]); + if (!oPrime.success) { + o.success = false; + return o; + } + for (std::map<std::string, Node>::iterator it = oPrime.map.begin(); + it != oPrime.map.end(); + it++) { + o.map[(*it).first] = (*it).second; + } + } + o.success = true; + } + return o; +} + + +// Fills in the pattern with a dictionary mapping variable names to +// nodes (these dicts are generated by match). Match and subst together +// create a full pattern-matching engine. +Node subst(Node pattern, + std::map<std::string, Node> dict, + std::string varflag, + Metadata m) { + // Swap out patterns at the token level + if (pattern.metadata.ln == -1) + pattern.metadata = m; + if (pattern.type == TOKEN && + pattern.val[0] == '$') { + if (dict.count(pattern.val.substr(1))) { + return dict[pattern.val.substr(1)]; + } + else { + return token(varflag + pattern.val.substr(1), m); + } + } + // Other tokens are untouched + else if (pattern.type == TOKEN) { + return pattern; + } + // Substitute recursively for ASTs + else { + std::vector<Node> args; + for (unsigned i = 0; i < pattern.args.size(); i++) { + args.push_back(subst(pattern.args[i], dict, varflag, m)); + } + return asn(pattern.val, args, m); + } +} + +// Transforms a sequence containing two-argument with statements +// into a statement containing those statements in nested form +Node withTransform (Node source) { + Node o = token("--"); + Metadata m = source.metadata; + std::vector<Node> args; + for (int i = source.args.size() - 1; i >= 0; i--) { + Node a = source.args[i]; + if (a.val == "with" && a.args.size() == 2) { + std::vector<Node> flipargs; + for (int j = args.size() - 1; j >= 0; j--) + flipargs.push_back(args[i]); + if (o.val != "--") + flipargs.push_back(o); + o = asn("with", a.args[0], a.args[1], asn("seq", flipargs, m), m); + args = std::vector<Node>(); + } + else { + args.push_back(a); + } + } + std::vector<Node> flipargs; + for (int j = args.size() - 1; j >= 0; j--) + flipargs.push_back(args[j]); + if (o.val != "--") + flipargs.push_back(o); + return asn("seq", flipargs, m); +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriteutils.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriteutils.h new file mode 100644 index 000000000..8abf44a9f --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/rewriteutils.h @@ -0,0 +1,51 @@ +#ifndef ETHSERP_REWRITEUTILS +#define ETHSERP_REWRITEUTILS + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// Valid functions and their min and max argument counts +extern std::string validFunctions[][3]; + +extern std::map<std::string, bool> vfMap; + +bool isValidFunctionName(std::string f); + +// Converts deep array access into ordered list of the arguments +// along the descent +std::vector<Node> listfyStorageAccess(Node node); + +// Cool function for debug purposes (named cerrStringList to make +// all prints searchable via 'cerr') +void cerrStringList(std::vector<std::string> s, std::string suffix=""); + +// Is the given node something of the form +// self.cow +// self.horse[0] +// self.a[6][7][self.storage[3]].chicken[9] +bool isNodeStorageVariable(Node node); + +// Applies rewrite rules adding without wrapper +Node rewriteChunk(Node inp); + +// Match result storing object +struct matchResult { + bool success; + std::map<std::string, Node> map; +}; + +// Match node to pattern +matchResult match(Node p, Node n); + +// Substitute node using pattern +Node subst(Node pattern, + std::map<std::string, Node> dict, + std::string varflag, + Metadata m); + +Node withTransform(Node source); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/serpent.py b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/serpent.py new file mode 100644 index 000000000..8d6bedfe3 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/serpent.py @@ -0,0 +1,201 @@ +import serpent_pyext as pyext +import sys +import re + +VERSION = '1.7.7' + + +class Metadata(object): + def __init__(self, li): + self.file = li[0] + self.ln = li[1] + self.ch = li[2] + + def out(self): + return [self.file, self.ln, self.ch] + + +class Token(object): + def __init__(self, val, metadata): + self.val = val + self.metadata = Metadata(metadata) + + def out(self): + return [0, self.val, self.metadata.out()] + + def __repr__(self): + return str(self.val) + + +class Astnode(object): + def __init__(self, val, args, metadata): + self.val = val + self.args = map(node, args) + self.metadata = Metadata(metadata) + + def out(self): + o = [1, self.val, self.metadata.out()]+[x.out() for x in self.args] + return o + + def __repr__(self): + o = '(' + self.val + subs = map(repr, self.args) + k = 0 + out = " " + while k < len(subs) and o != "(seq": + if '\n' in subs[k] or len(out + subs[k]) >= 80: + break + out += subs[k] + " " + k += 1 + if k < len(subs): + o += out + "\n " + o += '\n '.join('\n'.join(subs[k:]).split('\n')) + o += '\n)' + else: + o += out[:-1] + ')' + return o + + +def node(li): + if li[0]: + return Astnode(li[1], li[3:], li[2]) + else: + return Token(li[1], li[2]) + + +def take(x): + return pyext.parse_lll(x) if isinstance(x, (str, unicode)) else x.out() + + +def takelist(x): + return map(take, parse(x).args if isinstance(x, (str, unicode)) else x) + + +compile = lambda x: pyext.compile(x) +compile_chunk = lambda x: pyext.compile_chunk(x) +compile_to_lll = lambda x: node(pyext.compile_to_lll(x)) +compile_chunk_to_lll = lambda x: node(pyext.compile_chunk_to_lll(x)) +compile_lll = lambda x: pyext.compile_lll(take(x)) +parse = lambda x: node(pyext.parse(x)) +rewrite = lambda x: node(pyext.rewrite(take(x))) +rewrite_chunk = lambda x: node(pyext.rewrite_chunk(take(x))) +pretty_compile = lambda x: map(node, pyext.pretty_compile(x)) +pretty_compile_chunk = lambda x: map(node, pyext.pretty_compile_chunk(x)) +pretty_compile_lll = lambda x: map(node, pyext.pretty_compile_lll(take(x))) +serialize = lambda x: pyext.serialize(takelist(x)) +deserialize = lambda x: map(node, pyext.deserialize(x)) + +is_numeric = lambda x: isinstance(x, (int, long)) +is_string = lambda x: isinstance(x, (str, unicode)) +tobytearr = lambda n, L: [] if L == 0 else tobytearr(n / 256, L - 1)+[n % 256] + + +# A set of methods for detecting raw values (numbers and strings) and +# converting them to integers +def frombytes(b): + return 0 if len(b) == 0 else ord(b[-1]) + 256 * frombytes(b[:-1]) + + +def fromhex(b): + hexord = lambda x: '0123456789abcdef'.find(x) + return 0 if len(b) == 0 else hexord(b[-1]) + 16 * fromhex(b[:-1]) + + +def numberize(b): + if is_numeric(b): + return b + elif b[0] in ["'", '"']: + return frombytes(b[1:-1]) + elif b[:2] == '0x': + return fromhex(b[2:]) + elif re.match('^[0-9]*$', b): + return int(b) + elif len(b) == 40: + return fromhex(b) + else: + raise Exception("Cannot identify data type: %r" % b) + + +def enc(n): + if is_numeric(n): + return ''.join(map(chr, tobytearr(n, 32))) + elif is_string(n) and len(n) == 40: + return '\x00' * 12 + n.decode('hex') + elif is_string(n): + return '\x00' * (32 - len(n)) + n + elif n is True: + return 1 + elif n is False or n is None: + return 0 + + +def encode_datalist(*args): + if isinstance(args, (tuple, list)): + return ''.join(map(enc, args)) + elif not len(args) or args[0] == '': + return '' + else: + # Assume you're getting in numbers or addresses or 0x... + return ''.join(map(enc, map(numberize, args))) + + +def decode_datalist(arr): + if isinstance(arr, list): + arr = ''.join(map(chr, arr)) + o = [] + for i in range(0, len(arr), 32): + o.append(frombytes(arr[i:i + 32])) + return o + + +def encode_abi(funid, *args): + len_args = '' + normal_args = '' + var_args = '' + for arg in args: + if isinstance(arg, str) and len(arg) and \ + arg[0] == '"' and arg[-1] == '"': + len_args += enc(numberize(len(arg[1:-1]))) + var_args += arg[1:-1] + elif isinstance(arg, list): + for a in arg: + var_args += enc(numberize(a)) + len_args += enc(numberize(len(arg))) + else: + normal_args += enc(numberize(arg)) + return chr(int(funid)) + len_args + normal_args + var_args + + +def decode_abi(arr, *lens): + o = [] + pos = 1 + i = 0 + if len(lens) == 1 and isinstance(lens[0], list): + lens = lens[0] + while pos < len(arr): + bytez = int(lens[i]) if i < len(lens) else 32 + o.append(frombytes(arr[pos: pos + bytez])) + i, pos = i + 1, pos + bytez + return o + + +def main(): + if len(sys.argv) == 1: + print "serpent <command> <arg1> <arg2> ..." + else: + cmd = sys.argv[2] if sys.argv[1] == '-s' else sys.argv[1] + if sys.argv[1] == '-s': + args = [sys.stdin.read()] + sys.argv[3:] + elif sys.argv[1] == '-v': + print VERSION + sys.exit() + else: + cmd = sys.argv[1] + args = sys.argv[2:] + if cmd in ['deserialize', 'decode_datalist', 'decode_abi']: + args[0] = args[0].strip().decode('hex') + o = globals()[cmd](*args) + if isinstance(o, (Token, Astnode, list)): + print repr(o) + else: + print o.encode('hex') diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/setup.py b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/setup.py new file mode 100644 index 000000000..5fdc1c16a --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/setup.py @@ -0,0 +1,46 @@ +from setuptools import setup, Extension + +import os +from distutils.sysconfig import get_config_vars + +(opt,) = get_config_vars('OPT') +os.environ['OPT'] = " ".join( + flag for flag in opt.split() if flag != '-Wstrict-prototypes' +) + +setup( + # Name of this package + name="ethereum-serpent", + + # Package version + version='1.7.7', + + description='Serpent compiler', + maintainer='Vitalik Buterin', + maintainer_email='v@buterin.com', + license='WTFPL', + url='http://www.ethereum.org/', + + # Describes how to build the actual extension module from C source files. + ext_modules=[ + Extension( + 'serpent_pyext', # Python name of the module + ['bignum.cpp', 'util.cpp', 'tokenize.cpp', + 'lllparser.cpp', 'parser.cpp', 'functions.cpp', + 'optimize.cpp', 'opcodes.cpp', + 'rewriteutils.cpp', 'preprocess.cpp', 'rewriter.cpp', + 'compiler.cpp', 'funcs.cpp', 'pyserpent.cpp'] + )], + py_modules=[ + 'serpent', + 'pyserpent' + ], + scripts=[ + 'serpent.py' + ], + entry_points={ + 'console_scripts': [ + 'serpent = serpent:main', + ], + } + ), diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/tokenize.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/tokenize.cpp new file mode 100644 index 000000000..b60cc8a44 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/tokenize.cpp @@ -0,0 +1,115 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +// These appear as independent tokens even if inside a stream of symbols +const std::string atoms[] = { "#", "//", "(", ")", "[", "]", "{", "}" }; +const int numAtoms = 8; + +// Is the char alphanumeric, a space, a bracket, a quote, a symbol? +int chartype(char c) { + if (c >= '0' && c <= '9') return ALPHANUM; + else if (c >= 'a' && c <= 'z') return ALPHANUM; + else if (c >= 'A' && c <= 'Z') return ALPHANUM; + else if (std::string("~_$@").find(c) != std::string::npos) return ALPHANUM; + else if (c == '\t' || c == ' ' || c == '\n' || c == '\r') return SPACE; + else if (std::string("()[]{}").find(c) != std::string::npos) return BRACK; + else if (c == '"') return DQUOTE; + else if (c == '\'') return SQUOTE; + else return SYMB; +} + +// "y = f(45,124)/3" -> [ "y", "f", "(", "45", ",", "124", ")", "/", "3"] +std::vector<Node> tokenize(std::string inp, Metadata metadata, bool lispMode) { + int curtype = SPACE; + unsigned pos = 0; + int lastNewline = 0; + metadata.ch = 0; + std::string cur; + std::vector<Node> out; + + inp += " "; + while (pos < inp.length()) { + int headtype = chartype(inp[pos]); + if (lispMode) { + if (inp[pos] == '\'') headtype = ALPHANUM; + } + // Are we inside a quote? + if (curtype == SQUOTE || curtype == DQUOTE) { + // Close quote + if (headtype == curtype) { + cur += inp[pos]; + out.push_back(token(cur, metadata)); + cur = ""; + metadata.ch = pos - lastNewline; + curtype = SPACE; + pos += 1; + } + // eg. \xc3 + else if (inp.length() >= pos + 4 && inp.substr(pos, 2) == "\\x") { + cur += (std::string("0123456789abcdef").find(inp[pos+2]) * 16 + + std::string("0123456789abcdef").find(inp[pos+3])); + pos += 4; + } + // Newline + else if (inp.substr(pos, 2) == "\\n") { + cur += '\n'; + pos += 2; + } + // Backslash escape + else if (inp.length() >= pos + 2 && inp[pos] == '\\') { + cur += inp[pos + 1]; + pos += 2; + } + // Normal character + else { + cur += inp[pos]; + pos += 1; + } + } + else { + // Handle atoms ( '//', '#', brackets ) + for (int i = 0; i < numAtoms; i++) { + int split = cur.length() - atoms[i].length(); + if (split >= 0 && cur.substr(split) == atoms[i]) { + if (split > 0) { + out.push_back(token(cur.substr(0, split), metadata)); + } + metadata.ch += split; + out.push_back(token(cur.substr(split), metadata)); + metadata.ch = pos - lastNewline; + cur = ""; + curtype = SPACE; + } + } + // Special case the minus sign + if (cur.length() > 1 && (cur.substr(cur.length() - 1) == "-" + || cur.substr(cur.length() - 1) == "!")) { + out.push_back(token(cur.substr(0, cur.length() - 1), metadata)); + out.push_back(token(cur.substr(cur.length() - 1), metadata)); + cur = ""; + } + // Boundary between different char types + if (headtype != curtype) { + if (curtype != SPACE && cur != "") { + out.push_back(token(cur, metadata)); + } + metadata.ch = pos - lastNewline; + cur = ""; + } + cur += inp[pos]; + curtype = headtype; + pos += 1; + } + if (inp[pos] == '\n') { + lastNewline = pos; + metadata.ch = 0; + metadata.ln += 1; + } + } + return out; +} + + diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/tokenize.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/tokenize.h new file mode 100644 index 000000000..04a42f3c6 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/tokenize.h @@ -0,0 +1,16 @@ +#ifndef ETHSERP_TOKENIZE +#define ETHSERP_TOKENIZE + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" + +int chartype(char c); + +std::vector<Node> tokenize(std::string inp, + Metadata meta=Metadata(), + bool lispMode=false); + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/util.cpp b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/util.cpp new file mode 100644 index 000000000..56f642fc8 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/util.cpp @@ -0,0 +1,305 @@ +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include "util.h" +#include "bignum.h" +#include <fstream> +#include <cerrno> + +//Token or value node constructor +Node token(std::string val, Metadata met) { + Node o; + o.type = 0; + o.val = val; + o.metadata = met; + return o; +} + +//AST node constructor +Node astnode(std::string val, std::vector<Node> args, Metadata met) { + Node o; + o.type = 1; + o.val = val; + o.args = args; + o.metadata = met; + return o; +} + +//AST node constructors for a specific number of children +Node astnode(std::string val, Metadata met) { + std::vector<Node> args; + return astnode(val, args, met); +} + +Node astnode(std::string val, Node a, Metadata met) { + std::vector<Node> args; + args.push_back(a); + return astnode(val, args, met); +} + +Node astnode(std::string val, Node a, Node b, Metadata met) { + std::vector<Node> args; + args.push_back(a); + args.push_back(b); + return astnode(val, args, met); +} + +Node astnode(std::string val, Node a, Node b, Node c, Metadata met) { + std::vector<Node> args; + args.push_back(a); + args.push_back(b); + args.push_back(c); + return astnode(val, args, met); +} + +Node astnode(std::string val, Node a, Node b, Node c, Node d, Metadata met) { + std::vector<Node> args; + args.push_back(a); + args.push_back(b); + args.push_back(c); + args.push_back(d); + return astnode(val, args, met); +} + + +// Print token list +std::string printTokens(std::vector<Node> tokens) { + std::string s = ""; + for (unsigned i = 0; i < tokens.size(); i++) { + s += tokens[i].val + " "; + } + return s; +} + +// Prints a lisp AST on one line +std::string printSimple(Node ast) { + if (ast.type == TOKEN) return ast.val; + std::string o = "(" + ast.val; + std::vector<std::string> subs; + for (unsigned i = 0; i < ast.args.size(); i++) { + o += " " + printSimple(ast.args[i]); + } + return o + ")"; +} + +// Number of tokens in a tree +int treeSize(Node prog) { + if (prog.type == TOKEN) return 1; + int o = 0; + for (unsigned i = 0; i < prog.args.size(); i++) o += treeSize(prog.args[i]); + return o; +} + +// Pretty-prints a lisp AST +std::string printAST(Node ast, bool printMetadata) { + if (ast.type == TOKEN) return ast.val; + std::string o = "("; + if (printMetadata) { + o += ast.metadata.file + " "; + o += unsignedToDecimal(ast.metadata.ln) + " "; + o += unsignedToDecimal(ast.metadata.ch) + ": "; + } + o += ast.val; + std::vector<std::string> subs; + for (unsigned i = 0; i < ast.args.size(); i++) { + subs.push_back(printAST(ast.args[i], printMetadata)); + } + unsigned k = 0; + std::string out = " "; + // As many arguments as possible go on the same line as the function, + // except when seq is used + while (k < subs.size() && o != "(seq") { + if (subs[k].find("\n") != std::string::npos || (out + subs[k]).length() >= 80) break; + out += subs[k] + " "; + k += 1; + } + // All remaining arguments go on their own lines + if (k < subs.size()) { + o += out + "\n"; + std::vector<std::string> subsSliceK; + for (unsigned i = k; i < subs.size(); i++) subsSliceK.push_back(subs[i]); + o += indentLines(joinLines(subsSliceK)); + o += "\n)"; + } + else { + o += out.substr(0, out.size() - 1) + ")"; + } + return o; +} + +// Splits text by line +std::vector<std::string> splitLines(std::string s) { + unsigned pos = 0; + int lastNewline = 0; + std::vector<std::string> o; + while (pos < s.length()) { + if (s[pos] == '\n') { + o.push_back(s.substr(lastNewline, pos - lastNewline)); + lastNewline = pos + 1; + } + pos = pos + 1; + } + o.push_back(s.substr(lastNewline)); + return o; +} + +// Inverse of splitLines +std::string joinLines(std::vector<std::string> lines) { + std::string o = "\n"; + for (unsigned i = 0; i < lines.size(); i++) { + o += lines[i] + "\n"; + } + return o.substr(1, o.length() - 2); +} + +// Indent all lines by 4 spaces +std::string indentLines(std::string inp) { + std::vector<std::string> lines = splitLines(inp); + for (unsigned i = 0; i < lines.size(); i++) lines[i] = " "+lines[i]; + return joinLines(lines); +} + +// Binary to hexadecimal +std::string binToNumeric(std::string inp) { + std::string o = "0"; + for (unsigned i = 0; i < inp.length(); i++) { + o = decimalAdd(decimalMul(o,"256"), unsignedToDecimal((unsigned char)inp[i])); + } + return o; +} + +// Converts string to simple numeric format +std::string strToNumeric(std::string inp) { + std::string o = "0"; + if (inp == "") { + o = ""; + } + else if (inp.substr(0,2) == "0x") { + for (unsigned i = 2; i < inp.length(); i++) { + int dig = std::string("0123456789abcdef0123456789ABCDEF").find(inp[i]) % 16; + if (dig < 0) return ""; + o = decimalAdd(decimalMul(o,"16"), unsignedToDecimal(dig)); + } + } + else { + bool isPureNum = true; + for (unsigned i = 0; i < inp.length(); i++) { + isPureNum = isPureNum && inp[i] >= '0' && inp[i] <= '9'; + } + o = isPureNum ? inp : ""; + } + return o; +} + +// Does the node contain a number (eg. 124, 0xf012c, "george") +bool isNumberLike(Node node) { + if (node.type == ASTNODE) return false; + return strToNumeric(node.val) != ""; +} + +//Normalizes number representations +Node nodeToNumeric(Node node) { + std::string o = strToNumeric(node.val); + return token(o == "" ? node.val : o, node.metadata); +} + +Node tryNumberize(Node node) { + if (node.type == TOKEN && isNumberLike(node)) return nodeToNumeric(node); + return node; +} + +//Converts a value to an array of byte number nodes +std::vector<Node> toByteArr(std::string val, Metadata metadata, int minLen) { + std::vector<Node> o; + int L = 0; + while (val != "0" || L < minLen) { + o.push_back(token(decimalMod(val, "256"), metadata)); + val = decimalDiv(val, "256"); + L++; + } + std::vector<Node> o2; + for (int i = o.size() - 1; i >= 0; i--) o2.push_back(o[i]); + return o2; +} + +int counter = 0; + +//Makes a unique token +std::string mkUniqueToken() { + counter++; + return unsignedToDecimal(counter); +} + +//Does a file exist? http://stackoverflow.com/questions/12774207 +bool exists(std::string fileName) { + std::ifstream infile(fileName.c_str()); + return infile.good(); +} + +//Reads a file: http://stackoverflow.com/questions/2602013 +std::string get_file_contents(std::string filename) +{ + std::ifstream in(filename.c_str(), std::ios::in | std::ios::binary); + if (in) + { + std::string contents; + in.seekg(0, std::ios::end); + contents.resize(in.tellg()); + in.seekg(0, std::ios::beg); + in.read(&contents[0], contents.size()); + in.close(); + return(contents); + } + throw(errno); +} + +//Report error +void err(std::string errtext, Metadata met) { + std::string err = "Error (file \"" + met.file + "\", line " + + unsignedToDecimal(met.ln + 1) + ", char " + unsignedToDecimal(met.ch) + + "): " + errtext; + std::cerr << err << "\n"; + throw(err); +} + +//Bin to hex +std::string binToHex(std::string inp) { + std::string o = ""; + for (unsigned i = 0; i < inp.length(); i++) { + unsigned char v = inp[i]; + o += std::string("0123456789abcdef").substr(v/16, 1) + + std::string("0123456789abcdef").substr(v%16, 1); + } + return o; +} + +//Hex to bin +std::string hexToBin(std::string inp) { + std::string o = ""; + for (unsigned i = 0; i+1 < inp.length(); i+=2) { + char v = (char)(std::string("0123456789abcdef").find(inp[i]) * 16 + + std::string("0123456789abcdef").find(inp[i+1])); + o += v; + } + return o; +} + +//Lower to upper +std::string upperCase(std::string inp) { + std::string o = ""; + for (unsigned i = 0; i < inp.length(); i++) { + if (inp[i] >= 97 && inp[i] <= 122) o += inp[i] - 32; + else o += inp[i]; + } + return o; +} + +//Three-int vector +std::vector<int> triple(int a, int b, int c) { + std::vector<int> v; + v.push_back(a); + v.push_back(b); + v.push_back(c); + return v; +} diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/util.h b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/util.h new file mode 100644 index 000000000..f7d6744f9 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/serpent/util.h @@ -0,0 +1,127 @@ +#ifndef ETHSERP_UTIL +#define ETHSERP_UTIL + +#include <stdio.h> +#include <iostream> +#include <vector> +#include <map> +#include <fstream> +#include <cerrno> + +const int TOKEN = 0, + ASTNODE = 1, + SPACE = 2, + BRACK = 3, + SQUOTE = 4, + DQUOTE = 5, + SYMB = 6, + ALPHANUM = 7, + LPAREN = 8, + RPAREN = 9, + COMMA = 10, + COLON = 11, + UNARY_OP = 12, + BINARY_OP = 13, + COMPOUND = 14, + TOKEN_SPLITTER = 15; + +// Stores metadata about each token +class Metadata { + public: + Metadata(std::string File="main", int Ln=-1, int Ch=-1) { + file = File; + ln = Ln; + ch = Ch; + fixed = false; + } + std::string file; + int ln; + int ch; + bool fixed; +}; + +std::string mkUniqueToken(); + +// type can be TOKEN or ASTNODE +struct Node { + int type; + std::string val; + std::vector<Node> args; + Metadata metadata; +}; +Node token(std::string val, Metadata met=Metadata()); +Node astnode(std::string val, std::vector<Node> args, Metadata met=Metadata()); +Node astnode(std::string val, Metadata met=Metadata()); +Node astnode(std::string val, Node a, Metadata met=Metadata()); +Node astnode(std::string val, Node a, Node b, Metadata met=Metadata()); +Node astnode(std::string val, Node a, Node b, Node c, Metadata met=Metadata()); +Node astnode(std::string val, Node a, Node b, + Node c, Node d, Metadata met=Metadata()); + +// Number of tokens in a tree +int treeSize(Node prog); + +// Print token list +std::string printTokens(std::vector<Node> tokens); + +// Prints a lisp AST on one line +std::string printSimple(Node ast); + +// Pretty-prints a lisp AST +std::string printAST(Node ast, bool printMetadata=false); + +// Splits text by line +std::vector<std::string> splitLines(std::string s); + +// Inverse of splitLines +std::string joinLines(std::vector<std::string> lines); + +// Indent all lines by 4 spaces +std::string indentLines(std::string inp); + +// Converts binary to simple numeric format +std::string binToNumeric(std::string inp); + +// Converts string to simple numeric format +std::string strToNumeric(std::string inp); + +// Does the node contain a number (eg. 124, 0xf012c, "george") +bool isNumberLike(Node node); + +//Normalizes number representations +Node nodeToNumeric(Node node); + +//If a node is numeric, normalize its representation +Node tryNumberize(Node node); + +//Converts a value to an array of byte number nodes +std::vector<Node> toByteArr(std::string val, Metadata metadata, int minLen=1); + +//Reads a file +std::string get_file_contents(std::string filename); + +//Does a file exist? +bool exists(std::string fileName); + +//Report error +void err(std::string errtext, Metadata met); + +//Bin to hex +std::string binToHex(std::string inp); + +//Hex to bin +std::string hexToBin(std::string inp); + +//Lower to upper +std::string upperCase(std::string inp); + +//Three-int vector +std::vector<int> triple(int a, int b, int c); + +#define asn astnode +#define tkn token +#define msi std::map<std::string, int> +#define msn std::map<std::string, Node> +#define mss std::map<std::string, std::string> + +#endif diff --git a/Godeps/_workspace/src/github.com/ethereum/serpent-go/tests/main.go b/Godeps/_workspace/src/github.com/ethereum/serpent-go/tests/main.go new file mode 100644 index 000000000..2f2d17784 --- /dev/null +++ b/Godeps/_workspace/src/github.com/ethereum/serpent-go/tests/main.go @@ -0,0 +1,21 @@ +package main + +import ( + "fmt" + + "github.com/ethereum/serpent-go" +) + +func main() { + out, _ := serpent.Compile(` +// Namecoin +if !contract.storage[msg.data[0]]: # Is the key not yet taken? + # Then take it! + contract.storage[msg.data[0]] = msg.data[1] + return(1) +else: + return(0) // Otherwise do nothing + `) + + fmt.Printf("%x\n", out) +} |