Merge pull request #225 from WebAssembly/memory_pages

Make initial and max memory sizes be in pages instead of bytes

10 files changed, 92 insertions, 32 deletions

diff --git a/src/asm2wasm-main.cpp b/src/asm2wasm-main.cpp
index 5ab8bb0cf..73f6853d8 100644
--- a/src/asm2wasm-main.cpp
+++ b/src/asm2wasm-main.cpp
@@ -58,6 +58,11 @@ int main(int argc, const char *argv[]) {
   const auto &tm_it = options.extra.find("total memory");
   size_t totalMemory =
       tm_it == options.extra.end() ? 16 * 1024 * 1024 : atoi(tm_it->second.c_str());
+  if (totalMemory & ~Memory::kPageMask) {
+    std::cerr << "Error: total memory size " << totalMemory <<
+        " is not a multiple of the 64k wasm page size\n";
+    exit(EXIT_FAILURE);
+  }
 
   Asm2WasmPreProcessor pre;
   auto input(
@@ -75,7 +80,7 @@ int main(int argc, const char *argv[]) {
 
   if (options.debug) std::cerr << "wasming..." << std::endl;
   AllocatingModule wasm;
-  wasm.memory.initial = wasm.memory.max = totalMemory;
+  wasm.memory.initial = wasm.memory.max = totalMemory / Memory::kPageSize;
   Asm2WasmBuilder asm2wasm(wasm, pre.memoryGrowth, options.debug);
   asm2wasm.processAsm(asmjs);
 
diff --git a/src/binaryen-shell.cpp b/src/binaryen-shell.cpp
index 61cab723c..bfed8277e 100644
--- a/src/binaryen-shell.cpp
+++ b/src/binaryen-shell.cpp
@@ -111,10 +111,10 @@ struct ShellExternalInterface : ModuleInstance::ExternalInterface {
   ShellExternalInterface() : memory() {}
 
   void init(Module& wasm) override {
-    memory.resize(wasm.memory.initial);
+    memory.resize(wasm.memory.initial * wasm::Memory::kPageSize);
     // apply memory segments
     for (auto segment : wasm.memory.segments) {
-      assert(segment.offset + segment.size <= wasm.memory.initial);
+      assert(segment.offset + segment.size <= wasm.memory.initial * wasm::Memory::kPageSize);
       for (size_t i = 0; i != segment.size; ++i) {
         memory.set(segment.offset + i, segment.data[i]);
       }
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 91c4040f6..b69f7a977 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -284,6 +284,8 @@ struct PrintSExpression : public WasmVisitor<PrintSExpression, void> {
       case Shl:      o << "shl";      break;
       case ShrU:     o << "shr_u";    break;
       case ShrS:     o << "shr_s";    break;
+      case RotL:     o << "rotl";     break;
+      case RotR:     o << "rotr";     break;
       case Div:      o << "div";      break;
       case CopySign: o << "copysign"; break;
       case Min:      o << "min";      break;
diff --git a/src/s2wasm.h b/src/s2wasm.h
index b1c5f7c54..f87742bd0 100644
--- a/src/s2wasm.h
+++ b/src/s2wasm.h
@@ -55,7 +55,8 @@ class S2WasmBuilder {
         ignoreUnknownSymbols(ignoreUnknownSymbols),
         startFunction(startFunction),
         globalBase(globalBase),
-        nextStatic(globalBase) {
+        nextStatic(globalBase),
+        initialMemory(0) {
     s = input;
     scan();
     s = input;
@@ -75,6 +76,7 @@ class S2WasmBuilder {
   size_t globalBase, // where globals can start to be statically allocated, i.e., the data segment
          nextStatic; // location of next static allocation
   std::map<Name, int32_t> staticAddresses; // name => address
+  size_t initialMemory; // Initial size (in bytes) of memory (after linking, this is rounded and set on the wasm object in pages)
 
   struct Relocation {
     uint32_t* data;
@@ -396,7 +398,7 @@ class S2WasmBuilder {
       addressSegments[nextStatic] = wasm.memory.segments.size();
       wasm.memory.segments.emplace_back(
           nextStatic, reinterpret_cast<char*>(raw), pointerSize);
-      wasm.memory.initial = nextStatic + pointerSize;
+      initialMemory = nextStatic + pointerSize;
     }
     nextStatic += pointerSize;
   }
@@ -407,7 +409,7 @@ class S2WasmBuilder {
     nextStatic = (nextStatic + 15) & static_cast<size_t>(-16);
     staticAddresses[".stack"] = nextStatic;
     nextStatic += stackAllocation;
-    wasm.memory.initial = nextStatic;
+    initialMemory = nextStatic;
   }
 
   void process() {
@@ -1154,7 +1156,7 @@ class S2WasmBuilder {
       wasm.memory.segments.emplace_back(nextStatic, (const char*)&(*raw)[0], size);
     }
     nextStatic += size;
-    wasm.memory.initial = nextStatic;
+    initialMemory = nextStatic;
   }
 
   void parseLcomm(Name name, size_t align=1) {
@@ -1168,7 +1170,7 @@ class S2WasmBuilder {
     while (nextStatic % align) nextStatic++;
     staticAddresses[name] = nextStatic;
     nextStatic += size;
-    wasm.memory.initial = nextStatic;
+    initialMemory = nextStatic;
   }
 
   void skipImports() {
@@ -1183,6 +1185,11 @@ class S2WasmBuilder {
   }
 
   void fix() {
+    // Round the memory size up to a page, and update the page-increment versions
+    // of initial and max
+    wasm.memory.initial = ((initialMemory + Memory::kPageSize - 1) & Memory::kPageMask) /
+        Memory::kPageSize;
+
     auto ensureFunctionIndex = [&](Name name) {
       if (functionIndexes.count(name) == 0) {
         functionIndexes[name] = wasm.table.names.size();
diff --git a/src/support/bits.h b/src/support/bits.h
index bbafb29d4..6c9fbad94 100644
--- a/src/support/bits.h
+++ b/src/support/bits.h
@@ -17,6 +17,7 @@
 #ifndef wasm_support_bits_h
 #define wasm_support_bits_h
 
+#include <climits>
 #include <cstdint>
 #include <type_traits>
 
@@ -65,6 +66,20 @@ int CountLeadingZeroes(T v) {
   return CountLeadingZeroes(typename std::make_unsigned<T>::type(v));
 }
 
+template <typename T>
+inline static T RotateLeft(T val, T count) {
+  T mask = sizeof(T) * CHAR_BIT - 1;
+  count &= mask;
+  return (val << count) | (val >> (-count & mask));
+}
+template <typename T>
+inline static T RotateRight(T val, T count) {
+  T mask = sizeof(T) * CHAR_BIT - 1;
+  count &= mask;
+  return (val >> count) | (val << (-count & mask));
+}
+
+
 }  // namespace wasm
 
 #endif  // wasm_support_bits_h
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 8a03ca843..715c06287 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -287,6 +287,10 @@ enum ASTNodes {
   F64ConvertF32       = 0xb2,
   F64ReinterpretI64   = 0xb3,
   I64ReinterpretF64   = 0xb5,
+  I32RotR             = 0xb6,
+  I32RotL             = 0xb7,
+  I64RotR             = 0xb8,
+  I64RotL             = 0xb9,
   I32ReinterpretF32   = 0xfe, // XXX not in v8 spec doc
 
   I32LoadMem8S = 0x20,
@@ -402,18 +406,10 @@ public:
   void writeMemory() {
     if (wasm->memory.max == 0) return;
     if (debug) std::cerr << "== writeMemory" << std::endl;
-    o << int8_t(BinaryConsts::Memory);
-    if (wasm->memory.initial == 0) { // XXX diverge from v8, 0 means 0, 1 and above are powers of 2 starting at 0
-      o << int8_t(0);
-    } else {
-      o << int8_t(std::min(ceil(log2(wasm->memory.initial)), 31.0) + 1); // up to 31 bits, don't let ceil get us to UINT_MAX which can overflow
-    }
-    if (wasm->memory.max == 0) {
-      o << int8_t(0);
-    } else {
-      o << int8_t(std::min(ceil(log2(wasm->memory.max)), 31.0) + 1);
-    }
-    o << int8_t(1); // export memory
+    o << int8_t(BinaryConsts::Memory)
+      << LEB128(wasm->memory.initial)
+      << LEB128(wasm->memory.max)
+      << int8_t(1); // export memory
   }
 
   void writeSignatures() {
@@ -891,6 +887,8 @@ public:
       case Shl:      INT_TYPED_CODE(Shl);;
       case ShrU:     INT_TYPED_CODE(ShrU);
       case ShrS:     INT_TYPED_CODE(ShrS);
+      case RotL:     INT_TYPED_CODE(RotL);
+      case RotR:     INT_TYPED_CODE(RotR);
       case Div:      FLOAT_TYPED_CODE(Div);
       case CopySign: FLOAT_TYPED_CODE(CopySign);
       case Min:      FLOAT_TYPED_CODE(Min);
@@ -1088,10 +1086,8 @@ public:
 
   void readMemory() {
     if (debug) std::cerr << "== readMemory" << std::endl;
-    size_t initial = getInt8();
-    wasm.memory.initial = initial == 0 ? 0 : std::pow<size_t>(2, initial - 1);
-    size_t max = getInt8();
-    wasm.memory.max = max == 0 ? 0 : std::pow<size_t>(2, max - 1);
+    wasm.memory.initial = getLEB128();
+    wasm.memory.max = getLEB128();
     verifyInt8(1); // export memory
   }
 
@@ -1603,6 +1599,8 @@ public:
       INT_TYPED_CODE(Shl);
       INT_TYPED_CODE(ShrU);
       INT_TYPED_CODE(ShrS);
+      INT_TYPED_CODE(RotL);
+      INT_TYPED_CODE(RotR);
       FLOAT_TYPED_CODE(Div);
       FLOAT_TYPED_CODE(CopySign);
       FLOAT_TYPED_CODE(Min);
@@ -1671,4 +1669,3 @@ public:
 } // namespace wasm
 
 #endif // wasm_wasm_binary_h
-
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 223a9e1a5..f6a3e1027 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -102,7 +102,7 @@ public:
   Module& wasm;
 
   ModuleInstance(Module& wasm, ExternalInterface* externalInterface) : wasm(wasm), externalInterface(externalInterface) {
-    memorySize = wasm.memory.initial;
+    memorySize = wasm.memory.initial * Memory::kPageSize;
     externalInterface->init(wasm);
     if (wasm.start.is()) {
       LiteralList arguments;
@@ -464,6 +464,8 @@ private:
             case Shl:  return left.shl(right.and_(Literal(int32_t(31))));
             case ShrU: return left.shrU(right.and_(Literal(int32_t(31))));
             case ShrS: return left.shrS(right.and_(Literal(int32_t(31))));
+            case RotL: return left.rotL(right);
+            case RotR: return left.rotR(right);
             case Eq:   return left.eq(right);
             case Ne:   return left.ne(right);
             case LtS:  return left.ltS(right);
@@ -505,6 +507,8 @@ private:
             case Shl:  return left.shl(right.and_(Literal(int64_t(63))));
             case ShrU: return left.shrU(right.and_(Literal(int64_t(63))));
             case ShrS: return left.shrS(right.and_(Literal(int64_t(63))));
+            case RotL: return left.rotL(right);
+            case RotR: return left.rotR(right);
             case Eq:   return left.eq(right);
             case Ne:   return left.ne(right);
             case LtS:  return left.ltS(right);
diff --git a/src/wasm-js.cpp b/src/wasm-js.cpp
index 7b9afab30..000092da8 100644
--- a/src/wasm-js.cpp
+++ b/src/wasm-js.cpp
@@ -67,9 +67,14 @@ extern "C" void EMSCRIPTEN_KEEPALIVE load_asm2wasm(char *input) {
   Ref asmjs = builder.parseToplevel(input);
 
   module = new AllocatingModule();
-  module->memory.initial = EM_ASM_INT_V({
+  uint32_t providedMemory = EM_ASM_INT_V({
     return Module['providedTotalMemory']; // we receive the size of memory from emscripten
   });
+  if (providedMemory & ~Memory::kPageMask) {
+    std::cerr << "Error: provided memory is not a multiple of the 64k wasm page size\n";
+    exit(EXIT_FAILURE);
+  }
+  module->memory.initial = providedMemory / Memory::kPageSize;
   module->memory.max = pre.memoryGrowth ? -1 : module->memory.initial;
 
   if (wasmJSDebug) std::cerr << "wasming...\n";
@@ -114,9 +119,14 @@ extern "C" void EMSCRIPTEN_KEEPALIVE load_s_expr2wasm(char *input, char *mappedG
     abort();
   });
 
-  module->memory.initial = EM_ASM_INT_V({
+  uint32_t providedMemory = EM_ASM_INT_V({
     return Module['providedTotalMemory']; // we receive the size of memory from emscripten
   });
+  if (providedMemory & ~Memory::kPageMask) {
+    std::cerr << "Error: provided memory is not a multiple of the 64k wasm page size\n";
+    exit(EXIT_FAILURE);
+  }
+  module->memory.initial = providedMemory / Memory::kPageSize;
   module->memory.max = (module->exportsMap.find(GROW_WASM_MEMORY) != module->exportsMap.end()) ? -1 : module->memory.initial;
 
   // global mapping is done in js in post.js
@@ -151,7 +161,7 @@ extern "C" void EMSCRIPTEN_KEEPALIVE instantiate() {
       // create a new buffer here, just like native wasm support would.
       EM_ASM_({
         Module['outside']['newBuffer'] = new ArrayBuffer($0);
-      }, wasm.memory.initial);
+      }, wasm.memory.initial * Memory::kPageSize);
       for (auto segment : wasm.memory.segments) {
         EM_ASM_({
           var source = Module['HEAP8'].subarray($1, $1 + $2);
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index 1cd614c1d..cfabbf52d 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -430,7 +430,8 @@ public:
       WasmType type = stringToWasmType(str, false, true);
       // Local copy to index into op without bounds checking.
       constexpr size_t maxNameSize = 15;
-      char op[maxNameSize + 1] = { '\0' };
+      char op[maxNameSize + 1];
+      memset(op, 0, maxNameSize + 1); // ensure the whole string is cleared.
       strncpy(op, dot + 1, maxNameSize);
       switch (op[0]) {
         case 'a': {
@@ -523,6 +524,9 @@ public:
             if (op[2] == 'm') return makeBinary(s, op[4] == 'u' ? BinaryOp::RemU : BinaryOp::RemS, type);
             if (op[2] == 'i') return makeUnary(s, isWasmTypeFloat(type) ? UnaryOp::ReinterpretInt : UnaryOp::ReinterpretFloat, type);
           }
+          if (op[1] == 'o' && op[2] == 't') {
+            return makeBinary(s, op[3] == 'l' ? BinaryOp::RotL : BinaryOp::RotR, type);
+          }
           abort_on(op);
         }
         case 's': {
diff --git a/src/wasm.h b/src/wasm.h
index 6cbe93e3b..4bcb4bc87 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -503,6 +503,20 @@ public:
       default: WASM_UNREACHABLE();
     }
   }
+  Literal rotL(const Literal& other) const {
+    switch (type) {
+      case WasmType::i32: return Literal(RotateLeft(uint32_t(i32), uint32_t(other.i32)));
+      case WasmType::i64: return Literal(RotateLeft(uint64_t(i64), uint64_t(other.i64)));
+      default: WASM_UNREACHABLE();
+    }
+  }
+  Literal rotR(const Literal& other) const {
+    switch (type) {
+      case WasmType::i32: return Literal(RotateRight(uint32_t(i32), uint32_t(other.i32)));
+      case WasmType::i64: return Literal(RotateRight(uint64_t(i64), uint64_t(other.i64)));
+      default: WASM_UNREACHABLE();
+    }
+  }
 
   Literal eq(const Literal& other) const {
     switch (type) {
@@ -676,7 +690,7 @@ enum UnaryOp {
 
 enum BinaryOp {
   Add, Sub, Mul, // int or float
-  DivS, DivU, RemS, RemU, And, Or, Xor, Shl, ShrU, ShrS, // int
+  DivS, DivU, RemS, RemU, And, Or, Xor, Shl, ShrU, ShrS, RotL, RotR, // int
   Div, CopySign, Min, Max, // float
   // relational ops
   Eq, Ne, // int or float
@@ -1074,6 +1088,8 @@ public:
 
 class Memory {
 public:
+  static const size_t kPageSize = 64 * 1024;
+  static const size_t kPageMask = ~(kPageSize - 1);
   struct Segment {
     size_t offset;
     const char* data;
@@ -1082,7 +1098,7 @@ public:
     Segment(size_t offset, const char *data, size_t size) : offset(offset), data(data), size(size) {}
   };
 
-  size_t initial, max;
+  size_t initial, max; // sizes are in pages
   std::vector<Segment> segments;
 
   Memory() : initial(0), max((uint32_t)-1) {}