From 4d8f96dd88c97fa175952f8dd7ab548409c78b0e Mon Sep 17 00:00:00 2001 From: LemonBoy Date: Thu, 9 May 2019 23:46:12 +0200 Subject: Fix minor bug in LEB128 parsing --- std/debug/leb128.zig | 220 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 220 insertions(+) create mode 100644 std/debug/leb128.zig (limited to 'std/debug') diff --git a/std/debug/leb128.zig b/std/debug/leb128.zig new file mode 100644 index 0000000000..7bdb30a267 --- /dev/null +++ b/std/debug/leb128.zig @@ -0,0 +1,220 @@ +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: ShiftT = 0; + + while (true) { + const byte = try in_stream.readByte(); + + var operand: T = undefined; + if (@shlWithOverflow(T, byte & 0x7f, shift, &operand)) + return error.Overflow; + + result |= operand; + + if (@addWithOverflow(ShiftT, shift, 7, &shift)) + return error.Overflow; + + if ((byte & 0x80) == 0) + return result; + } +} + +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: ShiftT = 0; + var i: usize = 0; + + while (true) { + const byte = ptr.*[i]; + i += 1; + + var operand: T = undefined; + if (@shlWithOverflow(T, byte & 0x7f, shift, &operand)) + return error.Overflow; + + result |= operand; + + if (@addWithOverflow(ShiftT, shift, 7, &shift)) + return error.Overflow; + + if ((byte & 0x80) == 0) { + ptr.* += i; + return result; + } + } +} + +pub fn readILEB128(comptime T: type, in_stream: var) !T { + const ShiftT = @IntType(false, std.math.log2(T.bit_count)); + + var result: T = 0; + var shift: ShiftT = 0; + + while (true) { + const byte = u8(try in_stream.readByte()); + + var operand: T = undefined; + if (@shlWithOverflow(T, @intCast(T, byte & 0x7f), shift, &operand)) + return error.Overflow; + + result |= operand; + + if (@addWithOverflow(ShiftT, shift, 7, &shift)) + return error.Overflow; + + if ((byte & 0x80) == 0) { + if (shift <= ShiftT(T.bit_count - 1) and (byte & 0x40) != 0) { + result |= T(-1) << shift; + } + return result; + } + } +} + +pub fn readILEB128Mem(comptime T: type, ptr: *[*]const u8) !T { + const ShiftT = @IntType(false, std.math.log2(T.bit_count)); + + var result: T = 0; + var shift: ShiftT = 0; + var i: usize = 0; + + while (true) { + const byte = ptr.*[i]; + i += 1; + + var operand: T = undefined; + if (@shlWithOverflow(T, @intCast(T, byte & 0x7f), shift, &operand)) + return error.Overflow; + + result |= operand; + + if (@addWithOverflow(ShiftT, shift, 7, &shift)) + return error.Overflow; + + if ((byte & 0x80) == 0) { + if (shift <= ShiftT(T.bit_count - 1) and (byte & 0x40) != 0) { + result |= T(-1) << shift; + } + ptr.* += i; + return result; + } + } +} + +const OneByteReadInStream = struct { + const Error = error{NoError}; + const Stream = std.io.InStream(Error); + + stream: Stream, + str: []const u8, + curr: usize, + + fn init(str: []const u8) @This() { + return @This(){ + .stream = Stream{ .readFn = readFn }, + .str = str, + .curr = 0, + }; + } + + fn readFn(in_stream: *Stream, dest: []u8) Error!usize { + const self = @fieldParentPtr(@This(), "stream", in_stream); + if (self.str.len <= self.curr or dest.len == 0) + return 0; + + dest[0] = self.str[self.curr]; + self.curr += 1; + return 1; + } +}; + +fn test_read_ileb128(comptime T: type, encoded: []const u8) !T { + var in_stream = OneByteReadInStream.init(encoded); + const v1 = try readILEB128(T, &in_stream.stream); + var in_ptr = encoded.ptr; + const v2 = try readILEB128Mem(T, &in_ptr); + testing.expectEqual(v1, v2); + return v2; +} + +fn test_read_uleb128(comptime T: type, encoded: []const u8) !T { + var in_stream = OneByteReadInStream.init(encoded); + const v1 = try readULEB128(T, &in_stream.stream); + var in_ptr = encoded.ptr; + const v2 = try readULEB128Mem(T, &in_ptr); + return v2; +} + +test "deserialize signed LEB128" { + // Truncated + testing.expectError(error.EndOfStream, test_read_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")); + + // 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); + + // 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_uleb128(u64, "\x80")); + + // Overflow + testing.expectError(error.Overflow, test_read_uleb128(u8, "\x80\x80\x40")); + testing.expectError(error.Overflow, test_read_uleb128(u16, "\x80\x80\x80\x40")); + 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); + + // 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); +} -- cgit v1.2.3 From 1606dae7286daac67b5eb2d91108f558ab7b2b00 Mon Sep 17 00:00:00 2001 From: LemonBoy Date: Fri, 10 May 2019 10:26:43 +0200 Subject: Fix erroneous test case The *Mem variants cannot return EndOfStream and are generally unsafe to use. Proper order of checks, try both the variants and make sure they return the same error/result. Run the leb128.zig tests. --- std/debug/leb128.zig | 54 ++++++++++++++++++---------------------------------- std/std.zig | 2 ++ 2 files changed, 21 insertions(+), 35 deletions(-) (limited to 'std/debug') diff --git a/std/debug/leb128.zig b/std/debug/leb128.zig index 7bdb30a267..b8b960c975 100644 --- a/std/debug/leb128.zig +++ b/std/debug/leb128.zig @@ -108,53 +108,37 @@ pub fn readILEB128Mem(comptime T: type, ptr: *[*]const u8) !T { } } -const OneByteReadInStream = struct { - const Error = error{NoError}; - const Stream = std.io.InStream(Error); - - stream: Stream, - str: []const u8, - curr: usize, - - fn init(str: []const u8) @This() { - return @This(){ - .stream = Stream{ .readFn = readFn }, - .str = str, - .curr = 0, - }; - } - - fn readFn(in_stream: *Stream, dest: []u8) Error!usize { - const self = @fieldParentPtr(@This(), "stream", in_stream); - if (self.str.len <= self.curr or dest.len == 0) - return 0; +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); +} - dest[0] = self.str[self.curr]; - self.curr += 1; - return 1; - } -}; +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 = OneByteReadInStream.init(encoded); - const v1 = try readILEB128(T, &in_stream.stream); + var in_stream = std.io.SliceInStream.init(encoded); + const v1 = readILEB128(T, &in_stream.stream); var in_ptr = encoded.ptr; - const v2 = try readILEB128Mem(T, &in_ptr); + const v2 = readILEB128Mem(T, &in_ptr); testing.expectEqual(v1, v2); - return v2; + return v1; } fn test_read_uleb128(comptime T: type, encoded: []const u8) !T { - var in_stream = OneByteReadInStream.init(encoded); - const v1 = try readULEB128(T, &in_stream.stream); + var in_stream = std.io.SliceInStream.init(encoded); + const v1 = readULEB128(T, &in_stream.stream); var in_ptr = encoded.ptr; - const v2 = try readULEB128Mem(T, &in_ptr); - return v2; + const v2 = readULEB128Mem(T, &in_ptr); + testing.expectEqual(v1, v2); + return v1; } test "deserialize signed LEB128" { // Truncated - testing.expectError(error.EndOfStream, test_read_ileb128(i64, "\x80")); + testing.expectError(error.EndOfStream, test_read_stream_ileb128(i64, "\x80")); // Overflow testing.expectError(error.Overflow, test_read_ileb128(i8, "\x80\x80\x40")); @@ -188,7 +172,7 @@ test "deserialize signed LEB128" { test "deserialize unsigned LEB128" { // Truncated - testing.expectError(error.EndOfStream, test_read_uleb128(u64, "\x80")); + testing.expectError(error.EndOfStream, test_read_stream_uleb128(u64, "\x80")); // Overflow testing.expectError(error.Overflow, test_read_uleb128(u8, "\x80\x80\x40")); diff --git a/std/std.zig b/std/std.zig index e8df885e0d..8ec042fdb8 100644 --- a/std/std.zig +++ b/std/std.zig @@ -99,4 +99,6 @@ test "std" { _ = @import("unicode.zig"); _ = @import("valgrind.zig"); _ = @import("zig.zig"); + + _ = @import("debug/leb128.zig"); } -- cgit v1.2.3 From 6756e545f40dc7de373186a6581594e07bfd8200 Mon Sep 17 00:00:00 2001 From: LemonBoy Date: Sat, 11 May 2019 09:56:01 +0200 Subject: Fix more corner cases in LEB128 parsing --- std/debug/leb128.zig | 88 +++++++++++++++++++++++++++++++++------------------- 1 file changed, 56 insertions(+), 32 deletions(-) (limited to 'std/debug') diff --git a/std/debug/leb128.zig b/std/debug/leb128.zig index b8b960c975..2801877839 100644 --- a/std/debug/leb128.zig +++ b/std/debug/leb128.zig @@ -5,22 +5,24 @@ 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: ShiftT = 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, shift, &operand)) + if (@shlWithOverflow(T, byte & 0x7f, @intCast(ShiftT, shift), &operand)) return error.Overflow; result |= operand; - if (@addWithOverflow(ShiftT, shift, 7, &shift)) - return error.Overflow; - if ((byte & 0x80) == 0) return result; + + shift += 7; } } @@ -28,82 +30,92 @@ 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: ShiftT = 0; + var shift: usize = 0; var i: usize = 0; - while (true) { + while (true) : (i += 1) { const byte = ptr.*[i]; - i += 1; + + if (shift > T.bit_count) + return error.Overflow; var operand: T = undefined; - if (@shlWithOverflow(T, byte & 0x7f, shift, &operand)) + if (@shlWithOverflow(T, byte & 0x7f, @intCast(ShiftT, shift), &operand)) return error.Overflow; result |= operand; - if (@addWithOverflow(ShiftT, shift, 7, &shift)) - return error.Overflow; - 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: T = 0; - var shift: ShiftT = 0; + var result: UT = 0; + var shift: usize = 0; while (true) { const byte = u8(try in_stream.readByte()); - var operand: T = undefined; - if (@shlWithOverflow(T, @intCast(T, byte & 0x7f), shift, &operand)) + 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; - if (@addWithOverflow(ShiftT, shift, 7, &shift)) - return error.Overflow; + shift += 7; if ((byte & 0x80) == 0) { - if (shift <= ShiftT(T.bit_count - 1) and (byte & 0x40) != 0) { - result |= T(-1) << shift; + if (shift < T.bit_count and (byte & 0x40) != 0) { + result |= @bitCast(UT, @intCast(T, -1)) << @intCast(ShiftT, shift); } - return result; + 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: T = 0; - var shift: ShiftT = 0; + var result: UT = 0; + var shift: usize = 0; var i: usize = 0; - while (true) { + while (true) : (i += 1) { const byte = ptr.*[i]; - i += 1; - var operand: T = undefined; - if (@shlWithOverflow(T, @intCast(T, byte & 0x7f), shift, &operand)) + 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; - if (@addWithOverflow(ShiftT, shift, 7, &shift)) - return error.Overflow; + shift += 7; if ((byte & 0x80) == 0) { - if (shift <= ShiftT(T.bit_count - 1) and (byte & 0x40) != 0) { - result |= T(-1) << shift; + if (shift < T.bit_count and (byte & 0x40) != 0) { + result |= @bitCast(UT, @intCast(T, -1)) << @intCast(ShiftT, shift); } ptr.* += i; - return result; + return @bitCast(T, result); } } } @@ -145,6 +157,7 @@ test "deserialize signed LEB128" { 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); @@ -160,6 +173,13 @@ test "deserialize signed LEB128" { 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); @@ -175,8 +195,11 @@ test "deserialize unsigned LEB128" { 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")); @@ -193,6 +216,7 @@ test "deserialize unsigned LEB128" { 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); -- cgit v1.2.3 From 3d93c89fc55a428171bbfa779fb604801d84421d Mon Sep 17 00:00:00 2001 From: daurnimator Date: Sun, 5 May 2019 23:17:23 +1000 Subject: std: the failing allocator didn't actually count allocations Add a field '.allocations' to actually track the number of allocations. Additionally, only increment '.deallocations' when memory is freed --- std/debug/failing_allocator.zig | 18 +++++++++++++----- std/zig/parser_test.zig | 2 +- 2 files changed, 14 insertions(+), 6 deletions(-) (limited to 'std/debug') 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/zig/parser_test.zig b/std/zig/parser_test.zig index f2e80a9257..6977e4e6b1 100644 --- a/std/zig/parser_test.zig +++ b/std/zig/parser_test.zig @@ -2215,7 +2215,7 @@ fn testTransform(source: []const u8, expected_source: []const u8) !void { needed_alloc_count, failing_allocator.allocated_bytes, failing_allocator.freed_bytes, - failing_allocator.index, + failing_allocator.allocations, failing_allocator.deallocations, ); return error.MemoryLeakDetected; -- cgit v1.2.3