const std = @import("std"); const SourceMap = struct { const base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; const vlq_lookup_table: [256]VLQ = brk: { var entries: [256]VLQ = undefined; var i: usize = 0; var j: i32 = 0; while (i < 256) : (i += 1) { entries[i] = encodeVLQ(j); j += 1; } break :brk entries; }; const vlq_max_in_bytes = 8; pub const VLQ = struct { // We only need to worry about i32 // That means the maximum VLQ-encoded value is 8 bytes // because there are only 4 bits of number inside each VLQ value // and it expects i32 // therefore, it can never be more than 32 bits long // I believe the actual number is 7 bytes long, however we can add an extra byte to be more cautious bytes: [vlq_max_in_bytes]u8, len: u4 = 0, }; pub fn encodeVLQWithLookupTable( value: i32, ) VLQ { return if (value >= 0 and value <= 255) vlq_lookup_table[@intCast(usize, value)] else encodeVLQ(value); } // A single base 64 digit can contain 6 bits of data. For the base 64 variable // length quantities we use in the source map spec, the first bit is the sign, // the next four bits are the actual value, and the 6th bit is the continuation // bit. The continuation bit tells us whether there are more digits in this // value following this digit. // // Continuation // | Sign // | | // V V // 101011 // pub fn encodeVLQ( value: i32, ) VLQ { var len: u4 = 0; var bytes: [vlq_max_in_bytes]u8 = undefined; var vlq: u32 = if (value >= 0) @bitCast(u32, value << 1) else @bitCast(u32, (-value << 1) | 1); // source mappings are limited to i32 comptime var i: usize = 0; inline while (i < vlq_max_in_bytes) : (i += 1) { var digit = vlq & 31; vlq >>= 5; // If there are still more digits in this value, we must make sure the // continuation bit is marked if (vlq != 0) { digit |= 32; } bytes[len] = base64[digit]; len += 1; if (vlq == 0) { return VLQ{ .bytes = bytes, .len = len, }; } } return .{ .bytes = bytes, .len = 0 }; } pub const VLQResult = struct { value: i32 = 0, start: usize = 0, }; // base64 stores values up to 7 bits const base64_lut: [std.math.maxInt(u7)]u7 = brk: { @setEvalBranchQuota(9999); var bytes = [_]u7{std.math.maxInt(u7)} ** std.math.maxInt(u7); for (base64, 0..) |c, i| { bytes[c] = i; } break :brk bytes; }; pub fn decodeVLQ(encoded: []const u8, start: usize) VLQResult { var shift: u8 = 0; var vlq: u32 = 0; // hint to the compiler what the maximum value is const encoded_ = encoded[start..][0..@min(encoded.len - start, comptime (vlq_max_in_bytes + 1))]; // inlining helps for the 1 or 2 byte case, hurts a little for larger comptime var i: usize = 0; inline while (i < vlq_max_in_bytes + 1) : (i += 1) { const index = @as(u32, base64_lut[@truncate(u7, encoded_[i])]); // decode a byte vlq |= (index & 31) << @truncate(u5, shift); shift += 5; // Stop if there's no continuation bit if ((index & 32) == 0) { return VLQResult{ .start = i + start, .value = if ((vlq & 1) == 0) @intCast(i32, vlq >> 1) else -@intCast(i32, (vlq >> 1)), }; } } return VLQResult{ .start = start + encoded_.len, .value = 0 }; } }; pub fn main() anyerror!void { const args = try std.process.argsAlloc(std.heap.c_allocator); const how_many = try std.fmt.parseInt(u64, args[args.len - 1], 10); var numbers = try std.heap.c_allocator.alloc(i32, how_many); var results = try std.heap.c_allocator.alloc(SourceMap.VLQ, how_many); var leb_buf = try std.heap.c_allocator.alloc(u8, how_many * 8); const byte_size = std.mem.sliceAsBytes(numbers).len; var rand = std.rand.DefaultPrng.init(0); std.debug.print("Random values:\n\n", .{}); for (numbers, 0..) |_, i| { numbers[i] = rand.random().int(i32); } { var timer = try std.time.Timer.start(); for (numbers, 0..) |n, i| { results[i] = SourceMap.encodeVLQ(n); } const elapsed = timer.read(); std.debug.print("[{d}] encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); for (numbers, 0..) |n, i| { results[i] = SourceMap.encodeVLQWithLookupTable(n); } const elapsed = timer.read(); std.debug.print("[{d}] encodeWithLookupTable: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); for (results, 0..) |n, i| { numbers[i] = SourceMap.decodeVLQ(n.bytes[0..n.len], 0).value; } const elapsed = timer.read(); std.debug.print("[{d}] decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); var stream = std.io.fixedBufferStream(leb_buf); var writer = stream.writer(); for (numbers) |n| { std.leb.writeILEB128(writer, n) catch unreachable; } const elapsed = timer.read(); std.debug.print("[{d}] ILEB128 encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); var stream = std.io.fixedBufferStream(leb_buf); var reader = stream.reader(); for (numbers, 0..) |_, i| { numbers[i] = std.leb.readILEB128(i32, reader) catch unreachable; } const elapsed = timer.read(); std.debug.print("[{d}] ILEB128 decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } std.debug.print("\nNumbers between 0 - 8096:\n\n", .{}); for (numbers, 0..) |_, i| { numbers[i] = rand.random().intRangeAtMost(i32, 0, 8096); } { var timer = try std.time.Timer.start(); for (numbers, 0..) |n, i| { results[i] = SourceMap.encodeVLQ(n); } const elapsed = timer.read(); std.debug.print("[{d}] encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); for (numbers, 0..) |n, i| { results[i] = SourceMap.encodeVLQWithLookupTable(n); } const elapsed = timer.read(); std.debug.print("[{d}] encodeWithLookupTable: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); for (results, 0..) |n, i| { numbers[i] = SourceMap.decodeVLQ(n.bytes[0..n.len], 0).value; } const elapsed = timer.read(); std.debug.print("[{d}] decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); var stream = std.io.fixedBufferStream(leb_buf); var writer = stream.writer(); for (numbers) |n| { std.leb.writeILEB128(writer, n) catch unreachable; } const elapsed = timer.read(); std.debug.print("[{d}] ILEB128 encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); var stream = std.io.fixedBufferStream(leb_buf); var reader = stream.reader(); for (numbers, 0..) |_, i| { numbers[i] = std.leb.readILEB128(i32, reader) catch unreachable; } const elapsed = timer.read(); std.debug.print("[{d}] ILEB128 decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } std.debug.print("\nNumbers between 0 - 255:\n\n", .{}); for (numbers, 0..) |_, i| { numbers[i] = rand.random().intRangeAtMost(i32, 0, 255); } { var timer = try std.time.Timer.start(); for (numbers, 0..) |n, i| { results[i] = SourceMap.encodeVLQ(n); } const elapsed = timer.read(); std.debug.print("[{d}] encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); for (numbers, 0..) |n, i| { results[i] = SourceMap.encodeVLQWithLookupTable(n); } const elapsed = timer.read(); std.debug.print("[{d}] encodeWithLookupTable: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); for (results, 0..) |n, i| { numbers[i] = SourceMap.decodeVLQ(n.bytes[0..n.len], 0).value; } const elapsed = timer.read(); std.debug.print("[{d}] decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); var stream = std.io.fixedBufferStream(leb_buf); var writer = stream.writer(); for (numbers) |n| { std.leb.writeILEB128(writer, n) catch unreachable; } const elapsed = timer.read(); std.debug.print("[{d}] ILEB128 encode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } { var timer = try std.time.Timer.start(); var stream = std.io.fixedBufferStream(leb_buf); var reader = stream.reader(); for (numbers, 0..) |_, i| { numbers[i] = std.leb.readILEB128(i32, reader) catch unreachable; } const elapsed = timer.read(); std.debug.print("[{d}] ILEB128 decode: {} in {}\n", .{ how_many, std.fmt.fmtIntSizeDec(byte_size), std.fmt.fmtDuration(elapsed) }); } } test "encodeVLQ" { const fixtures = .{ .{ 2_147_483_647, "+/////D" }, .{ -2_147_483_647, "//////D" }, .{ 0, "A" }, .{ 1, "C" }, .{ -1, "D" }, .{ 123, "2H" }, .{ 123456789, "qxmvrH" }, }; inline for (fixtures) |fixture| { const result = SourceMap.encodeVLQ(fixture[0]); try std.testing.expectEqualStrings(fixture[1], result.bytes[0..result.len]); } } test "decodeVLQ" { const fixtures = .{ .{ 2_147_483_647, "+/////D" }, .{ -2_147_483_647, "//////D" }, .{ 0, "A" }, .{ 1, "C" }, .{ -1, "D" }, .{ 123, "2H" }, .{ 123456789, "qxmvrH" }, }; inline for (fixtures) |fixture| { const result = SourceMap.decodeVLQ(fixture[1], 0); try std.testing.expectEqual( result.value, fixture[0], ); } } option> Unnamed repository; edit this file 'description' to name the repository.
aboutsummaryrefslogtreecommitdiff
path: root/src/blob.zig (unfollow)
AgeCommit message (Expand)AuthorFilesLines
2022-07-23feat: add .PHONY on makefile targets (#847)Gravatar darker 1-19/+113
2022-07-22[bun install] Fix issue with URL path when sending requestGravatar Jarred Sumner 1-1/+55
2022-07-22Fix missing function bugbun-v0.1.5Gravatar Jarred Sumner 1-0/+1
2022-07-22[bun wiptest] This test does not seem to run?Gravatar Jarred Sumner 1-2/+2
2022-07-22`bun install` use custom BUN_CONFIG_REGISTRY port (#823)Gravatar SheetJSDev 1-1/+1
2022-07-22[docker] wipGravatar Jarred Sumner 3-13/+15
2022-07-22[docker] wipGravatar Jarred Sumner 1-2/+2
2022-07-22[docker] Use gcrGravatar Jarred Sumner 1-7/+21
2022-07-22[bun dev] Add flag to force hmrGravatar Jarred Sumner 1-3/+3
2022-07-22Fix link command on macOSGravatar Jarred Sumner 1-1/+1
2022-07-22[bun upgrade] Fix version display name for canary buildGravatar Jarred Sumner 1-1/+34
2022-07-22[bun upgrade] Fix name used in temporary dir for canary buildsGravatar Jarred Sumner 2-6/+26
2022-07-22WIP fix workflow runGravatar Jarred Sumner 1-1/+1
2022-07-22ClarifyGravatar Jarred Sumner 1-1/+1
2022-07-22Mention WSL version requirementGravatar Jarred Sumner 1-0/+2
2022-07-22Only run canary release on push to mainGravatar Jarred Sumner 1-4/+1
2022-07-22[bun upgrade] Implement `--canary` and `BUN_CANARY=1`Gravatar Jarred Sumner 3-20/+113
2022-07-22Fix mistake in Next.js Example README.Gravatar Aaditey Nair 1-1/+1
2022-07-22Update WebKitGravatar Jarred Sumner 1-0/+0
2022-07-22Workaround submodules issueGravatar Jarred Sumner 1-0/+4
2022-07-22Delete plus100-napiGravatar Jarred Sumner 1-0/+0
2022-07-22Rename linux amd64 -> linux x64Gravatar Jarred Sumner 1-18/+18
2022-07-22Mark as executableGravatar Jarred Sumner 4-11/+33
2022-07-22fix: remove suffix arg for mktemp compatibility (#825)Gravatar Connor Lurring 5-5/+5
2022-07-22Canary builds (Linux) (#824)canaryGravatar Jarred Sumner 12-220/+334
2022-07-21Separate Dockerfile for devcontainerGravatar Jarred Sumner 2-1/+100
2022-07-21BumpGravatar Jarred Sumner 1-1/+1
2022-07-21Redo the dockerfileGravatar Jarred SUmner 5-222/+203
2022-07-21docs(templates): Update README.md (#783)Gravatar Sakib Hasan 1-0/+8
2022-07-20chore(vscode): set tab size and tab format (#810)Gravatar Carter Snook 1-1/+2
2022-07-20feat(node/fs): implement more stat methods (#807)Gravatar Carter Snook 3-5/+108
2022-07-20doc: added an helper for the huge MakefileGravatar sanix-darker 1-6/+10
2022-07-20fix install script colorsGravatar Alexander 1-4/+6
2022-07-19Allow blankGravatar Jarred Sumner 1-1/+1
2022-07-19fix(api): stop double-free of prop array (#793)Gravatar Carter Snook 2-8/+6
2022-07-19refactor(installer): renovate install script (#745)Gravatar Wallunen 1-122/+162