Merge branch 'master' into rebased

2 files changed, 241 insertions, 5 deletions

diff --git a/std/debug/failing_allocator.zig b/std/debug/failing_allocator.zig
index 7a89460513..5776d23194 100644
--- a/std/debug/failing_allocator.zig
+++ b/std/debug/failing_allocator.zig
@@ -10,6 +10,7 @@ pub const FailingAllocator = struct {
     internal_allocator: *mem.Allocator,
     allocated_bytes: usize,
     freed_bytes: usize,
+    allocations: usize,
     deallocations: usize,
 
     pub fn init(allocator: *mem.Allocator, fail_index: usize) FailingAllocator {
@@ -19,6 +20,7 @@ pub const FailingAllocator = struct {
             .index = 0,
             .allocated_bytes = 0,
             .freed_bytes = 0,
+            .allocations = 0,
             .deallocations = 0,
             .allocator = mem.Allocator{
                 .reallocFn = realloc,
@@ -39,19 +41,25 @@ pub const FailingAllocator = struct {
             new_size,
             new_align,
         );
-        if (new_size <= old_mem.len) {
+        if (new_size < old_mem.len) {
             self.freed_bytes += old_mem.len - new_size;
-        } else {
+            if (new_size == 0)
+                self.deallocations += 1;
+        } else if (new_size > old_mem.len) {
             self.allocated_bytes += new_size - old_mem.len;
+            if (old_mem.len == 0)
+                self.allocations += 1;
         }
-        self.deallocations += 1;
         self.index += 1;
         return result;
     }
 
     fn shrink(allocator: *mem.Allocator, old_mem: []u8, old_align: u29, new_size: usize, new_align: u29) []u8 {
         const self = @fieldParentPtr(FailingAllocator, "allocator", allocator);
-        self.freed_bytes += old_mem.len - new_size;
-        return self.internal_allocator.shrinkFn(self.internal_allocator, old_mem, old_align, new_size, new_align);
+        const r = self.internal_allocator.shrinkFn(self.internal_allocator, old_mem, old_align, new_size, new_align);
+        self.freed_bytes += old_mem.len - r.len;
+        if (new_size == 0)
+            self.deallocations += 1;
+        return r;
     }
 };
diff --git a/std/debug/leb128.zig b/std/debug/leb128.zig
new file mode 100644
index 0000000000..2801877839
--- /dev/null
+++ b/std/debug/leb128.zig
@@ -0,0 +1,228 @@
+const std = @import("std");
+const testing = std.testing;
+
+pub fn readULEB128(comptime T: type, in_stream: var) !T {
+    const ShiftT = @IntType(false, std.math.log2(T.bit_count));
+
+    var result: T = 0;
+    var shift: usize = 0;
+
+    while (true) {
+        const byte = try in_stream.readByte();
+
+        if (shift > T.bit_count)
+            return error.Overflow;
+
+        var operand: T = undefined;
+        if (@shlWithOverflow(T, byte & 0x7f, @intCast(ShiftT, shift), &operand))
+            return error.Overflow;
+
+        result |= operand;
+
+        if ((byte & 0x80) == 0)
+            return result;
+
+        shift += 7;
+    }
+}
+
+pub fn readULEB128Mem(comptime T: type, ptr: *[*]const u8) !T {
+    const ShiftT = @IntType(false, std.math.log2(T.bit_count));
+
+    var result: T = 0;
+    var shift: usize = 0;
+    var i: usize = 0;
+
+    while (true) : (i += 1) {
+        const byte = ptr.*[i];
+
+        if (shift > T.bit_count)
+            return error.Overflow;
+
+        var operand: T = undefined;
+        if (@shlWithOverflow(T, byte & 0x7f, @intCast(ShiftT, shift), &operand))
+            return error.Overflow;
+
+        result |= operand;
+
+        if ((byte & 0x80) == 0) {
+            ptr.* += i;
+            return result;
+        }
+
+        shift += 7;
+    }
+}
+
+pub fn readILEB128(comptime T: type, in_stream: var) !T {
+    const UT = @IntType(false, T.bit_count);
+    const ShiftT = @IntType(false, std.math.log2(T.bit_count));
+
+    var result: UT = 0;
+    var shift: usize = 0;
+
+    while (true) {
+        const byte = u8(try in_stream.readByte());
+
+        if (shift > T.bit_count)
+            return error.Overflow;
+
+        var operand: UT = undefined;
+        if (@shlWithOverflow(UT, UT(byte & 0x7f), @intCast(ShiftT, shift), &operand)) {
+            if (byte != 0x7f)
+                return error.Overflow;
+        }
+
+        result |= operand;
+
+        shift += 7;
+
+        if ((byte & 0x80) == 0) {
+            if (shift < T.bit_count and (byte & 0x40) != 0) {
+                result |= @bitCast(UT, @intCast(T, -1)) << @intCast(ShiftT, shift);
+            }
+            return @bitCast(T, result);
+        }
+    }
+}
+
+pub fn readILEB128Mem(comptime T: type, ptr: *[*]const u8) !T {
+    const UT = @IntType(false, T.bit_count);
+    const ShiftT = @IntType(false, std.math.log2(T.bit_count));
+
+    var result: UT = 0;
+    var shift: usize = 0;
+    var i: usize = 0;
+
+    while (true) : (i += 1) {
+        const byte = ptr.*[i];
+
+        if (shift > T.bit_count)
+            return error.Overflow;
+
+        var operand: UT = undefined;
+        if (@shlWithOverflow(UT, UT(byte & 0x7f), @intCast(ShiftT, shift), &operand)) {
+            if (byte != 0x7f)
+                return error.Overflow;
+        }
+
+        result |= operand;
+
+        shift += 7;
+
+        if ((byte & 0x80) == 0) {
+            if (shift < T.bit_count and (byte & 0x40) != 0) {
+                result |= @bitCast(UT, @intCast(T, -1)) << @intCast(ShiftT, shift);
+            }
+            ptr.* += i;
+            return @bitCast(T, result);
+        }
+    }
+}
+
+fn test_read_stream_ileb128(comptime T: type, encoded: []const u8) !T {
+    var in_stream = std.io.SliceInStream.init(encoded);
+    return try readILEB128(T, &in_stream.stream);
+}
+
+fn test_read_stream_uleb128(comptime T: type, encoded: []const u8) !T {
+    var in_stream = std.io.SliceInStream.init(encoded);
+    return try readULEB128(T, &in_stream.stream);
+}
+
+fn test_read_ileb128(comptime T: type, encoded: []const u8) !T {
+    var in_stream = std.io.SliceInStream.init(encoded);
+    const v1 = readILEB128(T, &in_stream.stream);
+    var in_ptr = encoded.ptr;
+    const v2 = readILEB128Mem(T, &in_ptr);
+    testing.expectEqual(v1, v2);
+    return v1;
+}
+
+fn test_read_uleb128(comptime T: type, encoded: []const u8) !T {
+    var in_stream = std.io.SliceInStream.init(encoded);
+    const v1 = readULEB128(T, &in_stream.stream);
+    var in_ptr = encoded.ptr;
+    const v2 = readULEB128Mem(T, &in_ptr);
+    testing.expectEqual(v1, v2);
+    return v1;
+}
+
+test "deserialize signed LEB128" {
+    // Truncated
+    testing.expectError(error.EndOfStream, test_read_stream_ileb128(i64, "\x80"));
+
+    // Overflow
+    testing.expectError(error.Overflow, test_read_ileb128(i8, "\x80\x80\x40"));
+    testing.expectError(error.Overflow, test_read_ileb128(i16, "\x80\x80\x80\x40"));
+    testing.expectError(error.Overflow, test_read_ileb128(i32, "\x80\x80\x80\x80\x40"));
+    testing.expectError(error.Overflow, test_read_ileb128(i64, "\x80\x80\x80\x80\x80\x80\x80\x80\x80\x40"));
+    testing.expectError(error.Overflow, test_read_ileb128(i8, "\xff\x7e"));
+
+    // Decode SLEB128
+    testing.expect((try test_read_ileb128(i64, "\x00")) == 0);
+    testing.expect((try test_read_ileb128(i64, "\x01")) == 1);
+    testing.expect((try test_read_ileb128(i64, "\x3f")) == 63);
+    testing.expect((try test_read_ileb128(i64, "\x40")) == -64);
+    testing.expect((try test_read_ileb128(i64, "\x41")) == -63);
+    testing.expect((try test_read_ileb128(i64, "\x7f")) == -1);
+    testing.expect((try test_read_ileb128(i64, "\x80\x01")) == 128);
+    testing.expect((try test_read_ileb128(i64, "\x81\x01")) == 129);
+    testing.expect((try test_read_ileb128(i64, "\xff\x7e")) == -129);
+    testing.expect((try test_read_ileb128(i64, "\x80\x7f")) == -128);
+    testing.expect((try test_read_ileb128(i64, "\x81\x7f")) == -127);
+    testing.expect((try test_read_ileb128(i64, "\xc0\x00")) == 64);
+    testing.expect((try test_read_ileb128(i64, "\xc7\x9f\x7f")) == -12345);
+    testing.expect((try test_read_ileb128(i8, "\xff\x7f")) == -1);
+    testing.expect((try test_read_ileb128(i16, "\xff\xff\x7f")) == -1);
+    testing.expect((try test_read_ileb128(i32, "\xff\xff\xff\xff\x7f")) == -1);
+    testing.expect((try test_read_ileb128(i32, "\x80\x80\x80\x80\x08")) == -0x80000000);
+    testing.expect((try test_read_ileb128(i64, "\x80\x80\x80\x80\x80\x80\x80\x80\x80\x01")) == @bitCast(i64, @intCast(u64, 0x8000000000000000)));
+    testing.expect((try test_read_ileb128(i64, "\x80\x80\x80\x80\x80\x80\x80\x80\x40")) == -0x4000000000000000);
+    testing.expect((try test_read_ileb128(i64, "\x80\x80\x80\x80\x80\x80\x80\x80\x80\x7f")) == -0x8000000000000000);
+
+    // Decode unnormalized SLEB128 with extra padding bytes.
+    testing.expect((try test_read_ileb128(i64, "\x80\x00")) == 0);
+    testing.expect((try test_read_ileb128(i64, "\x80\x80\x00")) == 0);
+    testing.expect((try test_read_ileb128(i64, "\xff\x00")) == 0x7f);
+    testing.expect((try test_read_ileb128(i64, "\xff\x80\x00")) == 0x7f);
+    testing.expect((try test_read_ileb128(i64, "\x80\x81\x00")) == 0x80);
+    testing.expect((try test_read_ileb128(i64, "\x80\x81\x80\x00")) == 0x80);
+}
+
+test "deserialize unsigned LEB128" {
+    // Truncated
+    testing.expectError(error.EndOfStream, test_read_stream_uleb128(u64, "\x80"));
+
+    // Overflow
+    testing.expectError(error.Overflow, test_read_uleb128(u8, "\x80\x02"));
+    testing.expectError(error.Overflow, test_read_uleb128(u8, "\x80\x80\x40"));
+    testing.expectError(error.Overflow, test_read_uleb128(u16, "\x80\x80\x84"));
+    testing.expectError(error.Overflow, test_read_uleb128(u16, "\x80\x80\x80\x40"));
+    testing.expectError(error.Overflow, test_read_uleb128(u32, "\x80\x80\x80\x80\x90"));
+    testing.expectError(error.Overflow, test_read_uleb128(u32, "\x80\x80\x80\x80\x40"));
+    testing.expectError(error.Overflow, test_read_uleb128(u64, "\x80\x80\x80\x80\x80\x80\x80\x80\x80\x40"));
+
+    // Decode ULEB128
+    testing.expect((try test_read_uleb128(u64, "\x00")) == 0);
+    testing.expect((try test_read_uleb128(u64, "\x01")) == 1);
+    testing.expect((try test_read_uleb128(u64, "\x3f")) == 63);
+    testing.expect((try test_read_uleb128(u64, "\x40")) == 64);
+    testing.expect((try test_read_uleb128(u64, "\x7f")) == 0x7f);
+    testing.expect((try test_read_uleb128(u64, "\x80\x01")) == 0x80);
+    testing.expect((try test_read_uleb128(u64, "\x81\x01")) == 0x81);
+    testing.expect((try test_read_uleb128(u64, "\x90\x01")) == 0x90);
+    testing.expect((try test_read_uleb128(u64, "\xff\x01")) == 0xff);
+    testing.expect((try test_read_uleb128(u64, "\x80\x02")) == 0x100);
+    testing.expect((try test_read_uleb128(u64, "\x81\x02")) == 0x101);
+    testing.expect((try test_read_uleb128(u64, "\x80\xc1\x80\x80\x10")) == 4294975616);
+    testing.expect((try test_read_uleb128(u64, "\x80\x80\x80\x80\x80\x80\x80\x80\x80\x01")) == 0x8000000000000000);
+
+    // Decode ULEB128 with extra padding bytes
+    testing.expect((try test_read_uleb128(u64, "\x80\x00")) == 0);
+    testing.expect((try test_read_uleb128(u64, "\x80\x80\x00")) == 0);
+    testing.expect((try test_read_uleb128(u64, "\xff\x00")) == 0x7f);
+    testing.expect((try test_read_uleb128(u64, "\xff\x80\x00")) == 0x7f);
+    testing.expect((try test_read_uleb128(u64, "\x80\x81\x00")) == 0x80);
+    testing.expect((try test_read_uleb128(u64, "\x80\x81\x80\x00")) == 0x80);
+}